题解：P11838 [USACO25FEB] Printing Sequences B

考虑区间 dp，记

f_{i,j}

为从

i

至

j

的区间内最少要进行几次操作。

然后是区间 dp 的固定流程，第一层枚举区间长度，第二层枚举左右端点，第三层枚举区间内断点。

关键是如何计算一段区间内需要操作的次数。从题意可得知最优情况是将一段子区间重复多次，此时子区间内的不同元素个数会造成贡献。所以再枚举子区间长度，判断是否重复即可。转移方程为

f_{i,j} = \min(f_{i,j},cal(i,i+len-1))

。其中

len

是子区间长度，

cal

函数用来计算贡献。

时间复杂度

O(n^4)

。

CPP

#include <bits/stdc++.h>

using namespace std;

const int N = 105;
int n,m,a[N],f[N][N],v[N];

bool check(int x,int y,int l){
	for(int i=x;i<=y-l;i++)	if(a[i]!=a[i+l]) return false;
	return true;
}
int cal(int x,int y){
	int cnt=0;
	memset(v,0,sizeof v);
	for(int i=x;i<=y;i++) if(!v[a[i]]) cnt++,v[a[i]]=1;
	return cnt;
}
int main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int T; cin>>T;
	while(T--){
		cin>>n>>m;
		for(int i=1;i<=n;i++) cin>>a[i];
		memset(f,0x3f,sizeof f);
		for(int i=1;i<=n;i++) f[i][i]=1;
		for(int l=2;l<=n;l++){
			for(int i=1,j=i+l-1;j<=n;i++,j++){
				for(int k=i;k<j;k++) f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]);
				for(int k=i;k<j;k++){
					int len=k-i+1;
					if(l%len!=0) continue;
					if(check(i,j,len)) f[i][j]=min(f[i][j],cal(i,i+len-1));
				}
			}
		}
//		cout<<f[1][n]<<endl;
		if(f[1][n]<=m) cout<<"YES"<<endl;
		else cout<<"NO"<<endl;
	}    
	return 0;
}

题解：P11838 [USACO25FEB] Printing Sequences B

文章操作

相关推荐

评论

题解：P11838 [USACO25FEB] Printing Sequences B