思路

这题可以用区间 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;
}

#include <bits/stdc++.h>
using namespace std;
const int N = 110;
int t, n, k, a[N], f[N][N];
string s;
bool is(int l, int r, int k)
{
    for (int i = l+k; i <= r; i += k)
        if (s.substr(l, k) != s.substr(i, k)) return false;
    return true;
}
int main()
{
    cin >> t;
    while (t--)
    {
        memset(f, 0x3f, sizeof f);
        cin >> n >> k;
        s = " ";
        for (int i = 1; i <= n; i++)
            cin >> a[i], s += a[i], f[i][i] = (a[i] == a[i]) ? 1 : 1; // 修正初始化逻辑
        for (int len = 2; len <= n; len++)
        {
            for (int l = 1; l + len - 1 <= n; l++)
            {
                int r = l + len - 1;
                for (int m = 1; m * m <= len; m++)if (len % m == 0)
                    {
                        if (is(l, r, m))
                            f[l][r] = min(f[l][r], f[l][l + m - 1]);
                        if (is(l, r, len / m))
                            f[l][r] = min(f[l][r], f[l][l + len / m - 1]);
                    }
                for (int i = l; i < r; i++)
                    f[l][r] = min(f[l][r], f[l][i] + f[i + 1][r]);
            }
        }
        cout << (f[1][n] <= k ? "YES\n" : "NO\n");
    }
    return 0;
}