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 即可。

代码

#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 不能再压缩因为他们是不同价的。