【BZOJ3791】作业

2015.08.17 20:15 Mon | 45次阅读 | 旧日oi | 固定链接 | 源码

Description

给出一个n个数的01序列,开始每个点无色,每次可以任意选择一个区间将其染成颜色0或颜色1,共染k次,求最多能使得多少个点的值和颜色相同。
n<=100000,k<=50

题解

很容易证明,最终的状态最多只有2*k-1段,然后我们可以dp
用dp[i][j][k]表示前i个数分成j段末尾是颜色k能同色的点的最大值。
转移的话是O(1)的,
dp[i][j][k]=max(dp[i][j-1][k],dp[t][j-1][k^1]-sum[t][k]+sum[i][k]),sum是两种点的前缀和,这东西只要维护dp[t][j-1][k^1]-sum[t][k]的最大值就行了,

我的程序

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
#define N 100001
int n,k,mn0,mn1;
int a[N],sum[N][2],dp[N][100][2];
int main()
{
    cin>>n>>k;
    for(int i=1;i<=n;i++) 
    {
        scanf("%d",&a[i]);
        sum[i][0]=sum[i-1][0]+(a[i]==0);
        sum[i][1]=sum[i-1][1]+(a[i]==1);
    }
    if(2*k>n)
    {
        cout<<n<<endl;
        return 0;
    }
    for(int j=1;j<2*k;j++)
    {
        mn0=dp[j-1][j-1][0]-sum[j-1][1];
        mn1=dp[j-1][j-1][1]-sum[j-1][0];
        for(int i=j;i<=n;i++)
        {
            dp[i][j][0]=max(dp[i][j-1][0],sum[i][0]+mn1);
            dp[i][j][1]=max(dp[i][j-1][1],sum[i][1]+mn0);
            mn0=max(mn0,dp[i][j-1][0]-sum[i][1]);
            mn1=max(mn1,dp[i][j-1][1]-sum[i][0]);
        }
    }
    cout<<max(dp[n][2*k-1][0],dp[n][2*k-1][1])<<endl;
    return 0;
}```