题解：P11838 [USACO25FEB] Printing Sequences B

ksmgxeh · 2025-03-30 18:45:10 · 题解

考虑区间 dp，记 f_{i,j} 为从 i 至 j 的区间内最少要进行几次操作。

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

关键是如何计算一段区间内需要操作的次数。从题意可得知最优情况是将一段子区间重复多次，此时子区间内的不同元素个数会造成贡献。所以再枚举子区间长度，判断是否重复即可。转移方程为 f_{i,j} = \min(f_{i,j},cal(i,i+len-1))。其中 len 是子区间长度，cal 函数用来计算贡献。

时间复杂度 O(n^4)。

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