P11838 [USACO25FEB] Printing Sequences B 题解

思路

前置知识：区间 DP + kmp。

通过观察可以发现如果序列中有多个元素反复出现，则可以使用 REP 语句重复输出。要使 PRINT 语句少，则应该使用更多的 REP 语句，那么通过寻找最短循环节，就可以减少 PRINT 语句数量。我们可以设

f[i][j]

表示

i

到

j

至少使用的 PRINT 语句数量，如果

i

到

j

可以由一个最短循环节重复构成，那么

f[i][j]=f[i][i+minl-1]

，即次数等于输出最小循环节的次数，然后再通过枚举小区间合并转移。最后判断

f[1][n]

是否小于等于

k

即可。

代码

CPP

#include<bits/stdc++.h>
using namespace std; const int maxn=102;
int a[maxn],f[maxn][maxn],tem[maxn],nxt[maxn];
int sol(int l,int r){ // 计算最小循环节
	int cnt=r-l+1,j=0;
	for(int i=1;i<=cnt;i++) tem[i]=a[l-1+i],nxt[i]=0;
	for(int i=2;i<=cnt;i++){
		while(j&&tem[j+1]!=tem[i]) j=nxt[j];
		if(tem[j+1]==tem[i]) j++; nxt[i]=j;
	}
	if(cnt%(cnt-nxt[cnt])==0) return cnt-nxt[cnt];
	return -1;
}
int main(){
	int T; cin>>T; while(T--){
		int n,k; cin>>n>>k;
		for(int i=1;i<=n;i++) cin>>a[i];
		memset(f,0x3f3f3f3f,sizeof(f));
		for(int i=1;i<=n;i++) f[i][i]=1;
		for(int len=2;len<=n;len++) // 枚举区间长度。
			for(int st=1;st+len-1<=n;st++){ // 枚举区间起点。
				int la=st+len-1,minl=sol(st,la);
				if(minl!=-1) f[st][la]=f[st][st+minl-1];
				// 如果存在循环节，更新，因为循环节可以通过 REP 语句重复输出。
				for(int m=st;m<la;m++) // 枚举区间分割点
					f[st][la]=min(f[st][la],f[st][m]+f[m+1][la]);
			}
		if(f[1][n]<=k) cout<<"YES\n"; else cout<<"NO\n";
	}
	return 0;
}

本题是 UVA11022 的简单版，做完本题的可以完成这道题，需要注意没翻译到的是：不同阶的串是不能压缩的，不同阶的串指两个串被压缩的次数不同。

例如字符串 ABABB，压缩为

\texttt{(AB)}_2\texttt{B}

，此时后两个 B 不能再压缩因为他们是不同价的。

P11838 [USACO25FEB] Printing Sequences B 题解

文章操作

思路

代码

相关推荐

评论

P11838 [USACO25FEB] Printing Sequences B 题解