Teemo's hard problem (dp)

Teemo’s hard problem

题意

题目意思是给你一个数列，你可以任意反转[L,R]，使得这个数列的非递减序列最长。

看！代码

#include <bits/stdc++.h>
#define INF 0x3f3f3f3f3f3f3f3f
#define MOD 1000000007
using namespace std;
typedef long long ll;
int a[2010];
int pre[2010];//1的前缀长度（包括自己）
int suf[2010];//2的后缀长度（包括自己）
int dp[2005][2005][4];//[i,j]中以k结尾的最长非递增序列长度
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int n;
        scanf("%d",&n);
        memset(pre,0,sizeof(pre));
        memset(suf,0,sizeof(suf));
        memset(dp,0,sizeof(dp));
        for(int i=1; i<=n; i++)
        {
            scanf("%d",&a[i]);
            if(a[i]==1)pre[i]=pre[i-1]+1;
            else pre[i]=pre[i-1];
        }
        for(int i=n; i>=1; i--)
        {
            if(a[i]==2)suf[i]=suf[i+1]+1;
            else suf[i]=suf[i+1];
        }
        for(int i=1; i<=n; i++)
        {
            dp[i][i][a[i]]=1;
            for(int j=i+1; j<=n; j++)
            {
                if(a[j]==1)
                {
                    dp[i][j][1]=max(dp[i][j-1][1],dp[i][j-1][2])+1;
                    dp[i][j][2]=dp[i][j-1][2];
                }
                else if(a[j]==2)
                {
                    dp[i][j][1]=dp[i][j-1][1];
                    dp[i][j][2]=dp[i][j-1][2]+1;
                }
            }
        }
        int ans=0;
        for(int i=1; i<=n; i++)
            for(int j=i; j<=n; j++)
            {
                ans=max(ans,pre[i-1]+max(dp[i][j][1],dp[i][j][2])+suf[j+1]);
            }
        printf("%d\n",ans);
    }
    return 0;
}