BZOJ3791: 作业 dp

我们发现使用\(k\)次修改机会最多能产生\(2k+1\)段颜色，于是直接\(O(kn)\)水过即可。

不知道是不是正解，感觉很乱搞。

#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
using namespace std;
 
#define N 100010
#define M 110
int n,m,a[N],f[N][M][2];
 
int main(){
    #ifndef ONLINE_JUDGE
    freopen("tt.in","r",stdin);
    #endif
 
    scanf("%d%d",&n,&m);m=2*m-1;
    register int i,j,k;for(i=1;i<=n;++i)scanf("%d",&a[i]);
 
    f[1][1][1]=(a[1]==1),f[1][1][0]=(a[1]==0);
 
    for(i=2;i<=n;++i){
        for(j=1;j<=m;++j){
            f[i][j][0]=max(f[i][j][0],f[i-1][j][0]+(a[i]==0));
            if(j>1)f[i][j][0]=max(f[i][j][0],f[i-1][j-1][1]+(a[i]==0));
            f[i][j][1]=max(f[i][j][1],f[i-1][j][1]+(a[i]==1));
            if(j>1)f[i][j][1]=max(f[i][j][1],f[i-1][j-1][0]+(a[i]==1));
        }
    }
 
    int res=0;
    for(i=1;i<=n;++i)for(j=1;j<=m;++j)for(k=0;k<2;++k)res=max(res,f[i][j][k]);
 
    printf("%d",res);return 0;
}