CF2172L Maximum Color Segment 题解
Zskioaert1106
·
·
题解
题目传送门：CF2172L Maximum Color Segment
题意简述
给出长度为 n 的双色串，你可以进行至多 m 次操作，每次操作可以选出一个长度恰好为 k 的子串进行颜色反转，最大化其颜色段数。
题目分析
几个套路结论说是。首先极长段数等于邻项异或；其次奇偶项反转，等于统计邻项同色；然后做异或差分，等于统计 0 的数量；操作转化为了 i 和 i+k 同时反转，于是最后将模 k 的同余类拎出来，等于邻项同时反转。注意到 0,n 所在的两个同余类是特殊的，对其分讨一下边界，然后做背包 DP。
记拎出来的同余类序列为 $b$，则有 $f_{i,j,b_i} \leftarrow \max(f_{i-1,j,0},f_{i-1,j,1})$，$f_{i,j,\neg b_i} \leftarrow \max(f_{i-1,j-1,0}-1,f_{i-1,j-1,1}+1)$，然后 $f_{i,j,0}$ 加 $1$。
最后再用一个分组背包把所有同余类整合起来，$g_i \leftarrow g_{i-j} + \max(f_{j,0},f_{j,1})$，取 $0 \sim m$ 的最大值即可。
卡紧枚举上界，时间复杂度 $O(n^2)$，空间复杂度 $O(n)$。认为 $m$ 不比 $n$ 大。
### 代码实现
```cpp
#include<bits/stdc++.h>
using namespace std;
constexpr int N=3003;
int n,m,k,tot,ans,f[N][2],g[N];
bool a[N],b[N];
void solve(){
for(int i=1;i<tot;i++){
for(int j=tot;j;j--)
f[j][b[i]]=max(f[j][0],f[j][1]),
f[j][!b[i]]=max(f[j-1][0]-1,f[j-1][1]+1);
f[0][b[i]]=max(f[0][0],f[0][1]);
for(int j=b[i];j<=tot;j++)f[j][0]++; // 避免初始为 1 时 f[0][0] 污染
}
for(int i=m;i>=0;i--)
for(int j=0;j<=min(i,tot);j++)
g[i]=max(g[i],g[i-j]+max(f[j][0],f[j][1]));
}
int main(){
cin>>n>>m>>k;
for(int i=0;i<n;i++){
char c;
cin>>c;
a[i]=(c=='B')^(i&1);
}
for(int i=n;--i;)a[i]^=a[i-1];
{
tot=0;
for(int i=k;i<n;i+=k)b[tot++]=a[i];
memset(f,-0x3f,(tot+1)*8),f[0][b[0]]=!b[0],f[1][!b[0]]=b[0];
if(tot)solve(); // 注意要判空
}
if(n%k){
tot=0;
for(int i=n-k;i>0;i-=k)b[tot++]=a[i];
memset(f,-0x3f,(tot+1)*8),f[0][b[0]]=!b[0],f[1][!b[0]]=b[0];
solve();
}
for(int now=1;now<k;now++)
if(now!=n%k){
tot=0;
for(int i=now;i<n;i+=k)b[tot++]=a[i];
memset(f,-0x3f,(tot+1)*8),f[0][b[0]]=!b[0];
solve();
}
for(int i=0;i<=m;i++)ans=max(ans,g[i]);
cout<<ans+1;
return 0;
}
```
[AC 记录](https://codeforces.com/contest/2172/submission/398088717)。