BZOJ3791 作业 动态规划

你发现染 $k$ 次最多会将这个序列分成 $2k-1$ 段，然后任何 $2k-1$ 段以内的方案一定能被构建出来，所以直接 dp 就好了 

#include <bits/stdc++.h>
#define N 100004 
#define setIO(s) freopen(s".in","r",stdin) 
using namespace std;    
int A[N],f[N][104][2];        
int main() 
{
    int n,k,i,j;
    // setIO("input");  
    scanf("%d%d",&n,&k);         
    k=k*2-1;      
    for(i=1;i<=n;++i) scanf("%d",&A[i]);   
    int ans=0,p; 
    for(i=1;i<=n;++i) 
    {
        for(j=1;j<=k;++j) 
        {
            if(A[i]==0) 
            {
                f[i][j][0]=max(f[i-1][j-1][1]+1, f[i-1][j][0]+1); 
                f[i][j][1]=f[i-1][j][1];   
            }    
            else 
            {
                f[i][j][0]=f[i-1][j][0]; 
                f[i][j][1]=max(f[i-1][j-1][0]+1, f[i-1][j][1]+1);                    
            }
            ans=max(ans, f[i][j][0]); 
            ans=max(ans, f[i][j][1]); 
        }
    } 
    printf("%d
",ans);    
    return 0;         
}