题解：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

CPP

#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;
}

题解：CF2172L Maximum Color Segment

文章操作

Solution

Code

相关推荐

评论

题解：CF2172L Maximum Color Segment