题解：P11838 [USACO25FEB] Printing Sequences B

· · 题解

思路

这题可以用区间 DP 做，定义 dp_{i,j} 表示输出区间 [i,j] 至少需要多少个 PRINT 语句，dp_{i,j} 初始化为 \infty，dp_{i,i} 初始化为 1。

状态转移方程有两个，第一个是（显然）：

dp_{i,j} = \displaystyle\min_{i \le k < j}\{dp_{i,k}+dp_{k+1,j}\}

第二个是：

当区间 [i,j] 可以形成若干个长度为 k 的循环节时，

dp_{i,j} = \displaystyle\min_{1 \le k < j-i}\{dp_{i,i+k-1}\}

有了以上状态转移方程，代码就已经很好实现了。

代码实现

#include<iostream>
#include<cstring>
#include<string>
using namespace std;

int dp[110][110],a[110];

bool check(int l,int r,int k){
    string s="",s1="";
    int i;
    for(i = l; i < l+k; i++){
        s.push_back(a[i]+'0');
    }
    for(; i <= r; i++){
        s1.push_back(a[i]+'0');
        if(s1.size() == s.size()){
            if(s != s1){
                return false;
            }
            s1.clear();
        }
    }
    return true;
}

int main(){
    int t,n,k;
    for(cin>>t; t--; cout<<'\n'){
        cin>>n>>k;
        memset(dp,0x3f,sizeof dp);
        for(int i = 1; i <= n; i++){
            cin>>a[i];
            dp[i][i] = 1;
        }
        for(int d = 2; d <= n; d++){
            for(int i = 1; i+d-1 <= n; i++){
                int j = i+d-1;
                for(int k = i; k < j; k++){
                    dp[i][j] = min(dp[i][j],dp[i][k]+dp[k+1][j]);
                }
                for(int k = 1; k <= d/2; k++){
                    if(d%k==0 && check(i,j,k)){
                        dp[i][j] = min(dp[i][j],dp[i][i+k-1]);
                        break;
                    }
                }
            }
        }
        cout<<(dp[1][n]<=k ? "YES" : "NO");
    }
    return 0;
}