原题链接

1 题目

1.1 题目所需求出内容

对于本题，最终要求：能否达到最终的结果

1.2 题目背景、允许、禁止与限制

背景：有一个由 $n$ 个数组成的被期望输出的数列
允许：

• 使用不超过 $k$ 个 print 语句打印某个数，一个 print 语句只可以打印一个数字
• 还可以使用 repeat 语句，它的使用是无限次的，repeat可以重复print若干次，也就是说如果想输出 $1,1,2,2,2$ 只需要 $2$ 次print
  限制：最终要求求出能否使用不超过 $k$ 个 print 语句打印出期望序列

1.3 题目数据范围与猜测

$1 \le t,n \le 100 \longrightarrow O(tn^2)$

1.4 一句话概括题意

有一个被期望输出的数列，你需要判断是否可以使用无数次的repeat语句和至多 $k$ 次的print语句输出这个数列

2 题目破题推导

2.1 第一步：分情况考虑

我们考虑两种不同的情况

1. 普通串（如：$[1,2,3,1,4,5]$ ），这种串是无法用repeat语句解决的，因此只能选择最小的输出数量进行输出
2. 可以循环的串（如：$[1,2,1,2,1,2,1,2]$ ），这种串可以用repeat语句解决（相当于有循环节 $[1,2]$ ），因此尝试选择循环节数量最少的进行循环（如为了输出 $[1,2,1,2,1,2,1,2]$，应该选择循环节数量为 $4 \rightarrow[1,2]$ 而非循环节数量为 $2 \rightarrow[1,2,1,2]$）

那接下来我们想一下如何判断这个循环节是否存在呢？

2.2 第二步：数学

要想知道循环节是否存在，有三个东西必须要知道：分别是

• 序列（题目中已经给出）$a$
• 需要检查序列中某一区间的左右端点 $[l,r]$
• 循环节可能的长度 $len$

知道这三个之后，就要有两个条件

• 首先，需要保证区间长度是 $len$ 的倍数，也就是说 $r - l + 1~mod~len=0$

$A~mod~B=A\div B的余数$

• 其次，需要保证可能循环节中的每一项都和第一个循环节相对应的“相对位置”上的元素相同
  也就是 $a[now(当前这一项下标)]$ 时刻 $=a[l+(now~mod~len)]$
  举个例子：序列 $[1,2,1,2,3,1,2,3]$ 检测 $len=3$ 时就应保证

3 模型匹配

先提取关键词：时刻求取当前是否可行、区间
是 $\huge{区间动态规划}$

4 具体方案

4.1 动态规划定义（重点）

首先，先建立 dp 数组
设置 $dp[i][j]$ 打印区间 $[i,j]$ 范围内所需的最小print语句数量

4.2 初始化

都是 $0$
但是一格一定需要用一个print语句，因此对于每个 $i (1 \le i \le n)$，都要将 $dp[i][i]$ 设置为 $1$

4.3 状态转移方程

分两部分

• 先判断能否用repeat语句（特殊情况）的：
  枚举循环节长度 $k$ 从 $[l,\sqrt{r+l-1}]$，每次检查 $k$ 或者 $(r + l - 1) \div k$是否为循环节，不是则进入普通情况，否则可以记录 $dp[l][r]$ 为所有可能循环节长度 $k$ 的 $dp[l][l+k-1]$ 的最小值

• 一个是普通情况的：
  枚举区间 $[l,r]$ 之间的中间点 $k$，$dp[l][r]$ 就是所有 $dp[l][k]+dp[k+1][r]$ 中的最小值（大区间操作次数 $=$ 最小左区间操作次数+最小右区间操作次数）

4.4 答案求取

检查 $dp[1][n] \le k$ 是否成立

5 最终代码（禁止抄袭，仅用于参考）

#include <bits/stdc++.h>
using namespace std;

const int N = 111;
int t;
int a[N], dp[N][N];
bool check(int l, int r, int k){
	if ((r - l + 1) % k != 0){
		return false;
	}
	for (int i = l;i <= r;i++){
		int pos = l + ((i - l) % k);
		if (a[i] != a[pos]){
			return false;
		}
	}
	return true;
}

int main(){
	
	cin >> t;
	while(t--){
		int n, k;
		memset(dp, 0x3f, sizeof(dp));
		cin >> n >> k;
		for (int i = 1;i <= n;i++){
			cin >> a[i];
			dp[i][i] = 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 (check(l, r, m)){
							dp[l][r] = min(dp[l][r], dp[l][l + m - 1]);
						}
						if (check(l, r, len / m)){
							dp[l][r] = min(dp[l][r], dp[l][l + len / m - 1]);
						}
					}
				}
				for (int k = l;k <= r;k++){
					dp[l][r] = min(dp[l][r], dp[l][k] + dp[k + 1][r]);
				}
			}
		}
		cout << (dp[1][n] <= k ? "YES" : "NO") << endl;
	}
	
	return 0;
}