codeforces 1272D（dp）

题意描述

You are given an array a consisting of n integers.

You can remove at most one element from this array. Thus, the final length of the array is n−1 or n.

Your task is to calculate the maximum possible length of the strictly increasing contiguous subarray of the remaining array.

Recall that the contiguous subarray a with indices from l to r is a[l…r]=al,al+1,…,ar. The subarray a[l…r] is called strictly increasing if al<al+1<⋯<ar.

最多可以删除一个数字，求最长上升子序列

思路

我们使用dp[i][j]来表示状态，j为0表示没有删除过数字，j为1表示删除过数字。则dp[i][0]表示没有删除过数字时a[i]以前最长子序列的长度，dp[i][1]表示删除过数字时a[i]以前最长子序列的长度。如果a[i]>a[i-1]那么转移公式为 f [ i ] [ 0 ] = m a x ( f [ i − 1 ] [ 0 ] + 1 , f [ i ] [ 0 ] ) ; f[i][0]=max(f[i-1][0]+1,f[i][0]); f[i][0]=max(f[i−1][0]+1,f[i][0]); f [ i ] [ 1 ] = m a x ( f [ i − 1 ] [ 1 ] + 1 , f [ i ] [ 1 ] ) ; f[i][1]=max(f[i-1][1]+1,f[i][1]); f[i][1]=max(f[i−1][1]+1,f[i][1]); 如果需要删除一个数，那么显然a[i]要和a[i-2]进行比较，得到转移公式 f [ i ] [ 1 ] = m a x ( f [ i ] [ 1 ] , f [ i − 2 ] [ 0 ] + 1 ) ; f[i][1]=max(f[i][1],f[i-2][0]+1); f[i][1]=max(f[i][1],f[i−2][0]+1);

AC代码

#include<bits/stdc++.h>
#define x first
#define y second
#define PB push_back
#define mst(x,a) memset(x,a,sizeof(x))
#define all(a) begin(a),end(a)
#define rep(x,l,u) for(ll x=l;x<u;x++)
#define rrep(x,l,u) for(ll x=l;x>=u;x--)
#define IOS ios::sync_with_stdio(false);cin.tie(0);
using namespace std;
typedef unsigned long long ull;
typedef pair<int,int> PII;
typedef pair<long,long> PLL;
typedef pair<char,char> PCC;
typedef long long ll;
const int N=2*1e5+10;
const int M=1e6+10;
const int INF=0x3f3f3f3f;
const int MOD=1e9+7;
int f[N][2],a[N];
void solve(){
    int n;cin>>n;
    rep(i,1,n+1) cin>>a[i];
    f[1][0]=1;//初值条件
    int res=-1;
    rep(i,2,n+1){
        f[i][0]=f[i][1]=1;
        if(a[i]>a[i-1]){
            f[i][0]=max(f[i][0],f[i-1][0]+1);
            f[i][1]=max(f[i][1],f[i-1][1]+1);
        }
        if(a[i]>a[i-2]){
            f[i][1]=max(f[i][1],f[i-2][0]+1);
        }
        res=max(res,max(f[i][1],f[i][0]));
    }
    cout<<res<<endl;
}
int main(){
    IOS;
    solve();
    return 0;
}