题解：CF2172L Maximum Color Segment

· · 题解

Solution

感觉不是很难，不懂为什么这么少人过。

首先考虑经典差分转化，相邻两项分别异或起来得到新序列。

那么原题中进行长为 k 的翻转就变为了对于相隔 k 的两点翻转，极长颜色段个数就是新序列中 1 的个数。

容易发现可以每个 k 的同余系中的问题是独立的，分别拉出来做 O(k) 次即可。

那么问题就转变为了可以进行若干次翻转相邻两位的操作，求最多能得到多少个 1，直接令 f_i 表示进行 i 次操作能够新增加的 1 的个数即可，转移以及优化都是平凡的。

然后最后考虑把 m 次操作分配个 O(k) 个序列，使得总贡献最大，直接分组背包即可。

但现在有个问题就是如果直接做，分组背包时间复杂度是 O(km^2) 的，考虑优化。

发现如果 k 很大，那么每个小区间的长度就会减小，肯定使用不满 m 次就能使所有数变为 1。

我们贪心的想一下，怎样构造一个 01 序列能够使全变为 1 的操作数尽可能多，不难发现这个东西是与序列长度同阶的（可能要乘上一个常数）。

所以我们只需要对于每个序列枚举到 O(\dfrac{n}{k}) 次操作即可，时间复杂度 O(nm)。

最后还要考虑一个小 corner case，就是原序列开头与结尾的翻转，可以单独一个数翻转，这时候会多出一条转移式，特判一下即可。

Code

#include<bits/stdc++.h>
#define int long long
#define N 3005
using namespace std;
int n,m,k,a[N],dp[3][N],f[N][N],g[N];
int fl,tot,d[N],t,ans;
char ch,lst;
vector<int>vt[N];
signed main(){
    ios::sync_with_stdio(false);
    cin>>n>>m>>k,fl=n%k,t=min(m,3*(n/k+5));
    for(int i=0;i<n;i++){
        cin>>ch;
        if(!i){lst=ch;continue;}
        a[i]=(lst!=ch),ans+=a[i],vt[i%k].push_back(a[i]),lst=ch;
    }
    for(int id=0;id<k;id++){
        tot=0;
        for(int i=0;i<vt[id].size();i++){
            if(!vt[id][i]) d[++tot]=i+1;
        }
        for(int i=1;i<=t;i++)
            dp[0][i]=dp[1][i]=dp[2][i]=0;
        for(int i=1;i<=tot;i++){
            for(int j=t;j;j--){
                dp[0][j]=0;
                if(i>=2&&j>=d[i]-d[i-1])
                    dp[0][j]=max(dp[0][j],dp[2][j-(d[i]-d[i-1])]+2);
                if(!id&&j>=d[i])
                    dp[0][j]=max(dp[0][j],dp[1][j-d[i]]+1);
                if(id==fl&&j>=vt[id].size()-d[i]+1)
                    dp[0][j]=max(dp[0][j],dp[1][j-(vt[id].size()-d[i]+1)]+1);
            }
            for(int j=1;j<=t;j++)
                dp[2][j]=max(dp[2][j],dp[1][j]),
                dp[1][j]=max(dp[1][j],dp[0][j]);
        }
        for(int i=1;i<=t;i++) f[id][i]=dp[0][i];
    }
    for(int i=0;i<k;i++){
        for(int j=m;j;j--){
            for(int l=1;l<=t;l++){
                if(j>=l) g[j]=max(g[j],g[j-l]+f[i][l]);
            }
        }
    }
    cout<<g[m]+ans+1;
    return 0;
}