Codeforces 933A (动态规划)-白红宇

Codeforces 933A (动态规划)

阅读量：5142 次

发布时间：2019-06-13

本文共 2095 字，大约阅读时间需要 6 分钟。

题目链接：http://codeforces.com/contest/934/problem/C

因为最后要找的是一段单调非减区间，所以最后形成的序列一定是11...12....22。中间有一个从1到2的断点。

现在要找一个区间反转，如果反转之后形成的序列的断点不在这个区间内，那么这次反转就没有任何意义，所以在dp区间里，断点必须包含在其中。

开一个三维数组dp[2010][2010][2];

dp[i][j][0]代表【i，j】区间中数字的状态，1代表全是1,2代表全是2,3代表1和2都有。

dp[i][j][1]代表【i，j】区间中最长非递增子序列的最大长度。

再开三个数组a,b，c，a[i]代表在i之前有多少个1，b[i]表示在i之后有多少个2，c[i]表示在i之前有多少个2（都不包括i位置，其中c当做前缀数组使用）

在dp的过程中考量dp[i][j][1]+a[i]+b[j]的大小，取最大值就是最后的答案。

#include
     
      #include
      
       #include
       
        #include
        
         #include
         #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #define LL long long#define mod 1000000007#define inf 0x3f3f3f3fusing namespace std;int num[2010];int a[2010];int b[2010];int c[2010];int dp[2010][2010][2];int main(){ int n; while(~scanf("%d",&n)) { memset(num,0,sizeof(num)); memset(a,0,sizeof(a)); memset(b,0,sizeof(b)); memset(c,0,sizeof(c)); memset(dp,0,sizeof(dp)); for(int i=1;i<=n;i++) { scanf("%d",&num[i]); } a[1]=0; b[n]=0; int p=0; if(num[1]==1) p++; for(int i=2;i<=n;i++) { a[i]=p; if(num[i]==1) p++; //printf("%d ",a[i]); } p=0; if(num[n]==2) p++; for(int i=n-1;i>=1;i--) { b[i]=p; if(num[i]==2) p++; } p=0; for(int i=1;i<=n;i++) { if(num[i]==2) c[i]=++p; else c[i]=p; } int maxx=-1; for(int i=1;i<=n;i++) for(int j=i;j<=n;j++) { if(i==j) { dp[i][j][1]=1; if(num[i]==1) dp[i][j][0]=1; else dp[i][j][0]=2; } else if(num[j]==1) { if(dp[i][j-1][0]==1) { dp[i][j][1]=dp[i][j-1][1]+1; dp[i][j][0]=1; } else if(dp[i][j-1][0]==2) { dp[i][j][1]=dp[i][j-1][1]+1; dp[i][j][0]=3; } else { dp[i][j][1]=dp[i][j-1][1]+1; dp[i][j][0]=3; } } else if(num[j]==2) { if(dp[i][j-1][0]==1) { dp[i][j][1]=1; dp[i][j][0]=3; } else if(dp[i][j-1][0]==2) { dp[i][j][1]=dp[i][j-1][1]+1; dp[i][j][0]=2; } else { if(c[j]-c[i-1]>=dp[i][j-1][1]) { dp[i][j][0]=2; dp[i][j][1]=c[j]-c[i-1]; } else { dp[i][j][0]=3; dp[i][j][1]=dp[i][j-1][1]; } } } //printf("dp %d %d:%d %d %d %d\n",i,j,dp[i][j][1],a[i],b[j],dp[i][j][1]+a[i]+b[j]); maxx=max(maxx,dp[i][j][1]+a[i]+b[j]); } printf("%d\n",maxx); } return 0;}

转载于:https://www.cnblogs.com/brotherHaiNo1/p/8450190.html

你可能感兴趣的文章