原题链接
1 题目
1.1 题目所需求出内容
对于本题，最终要求：能否达到最终的结果
1.2 题目背景、允许、禁止与限制
背景：有一个由 nnn 个数组成的被期望输出的数列
允许：
* 使用不超过 kkk 个 print 语句打印某个数，一个 print 语句只可以打印一个数字
* 还可以使用 repeat 语句，它的使用是无限次的，repeat可以重复print若干次，也就是说如果想输出 1,1,2,2,21,1,2,2,21,1,2,2,2 只需要 222 次print
禁止：
限制：最终要求求出能否使用不超过 kkk 个 print 语句打印出期望序列
1.3 题目数据范围与猜测
1≤t,n≤100⟶O(tn2)1 \le t,n \le 100 \longrightarrow O(tn^2)1≤t,n≤100⟶O(tn2)
1.4 一句话概括题意
有一个被期望输出的数列，你需要判断是否可以使用无数次的repeat语句（规则上面讲了）和至多 kkk 次的print语句输出这个数列
2 题目破题推导
> 注：以下七种方法都可以考虑一下
2.1 大拆小、小组大
2.2 正向思维转逆向思维，逆向思维转正向思维
2.3 以终为始、以始为终
2.4 数学
先看2.5部分
要想知道循环节是否存在，有三个东西必须要知道：分别是
* 序列（题目中已经给出）aaa
* 需要检查序列中某一区间的左右端点 [l,r][l,r][l,r]
* 循环节可能的长度 lenlenlen
知道这三个之后，就要有两个条件
* 首先，需要保证区间长度是 lenlenlen 的倍数，也就是说 r−l+1 mod len=0r - l + 1~mod~len=0r−l+1 mod len=0
> A mod B=A÷B的余数A~mod~B=A\div B的余数A mod B=A÷B的余数
* 其次，需要保证可能循环节中的每一项都和第一个循环节相对应的“相对位置”上的元素相同
也就是 anow(当前这一项下标)a_{now(当前这一项下标)}anow(当前这一项下标) 时刻 =al+(now mod len)=a_{l+(now~mod~len)}=al+(now mod len)
举个例子：序列 [1,2,1,2,3,1,2,3][1,2,1,2,3,1,2,3][1,2,1,2,3,1,2,3] 检测 len=3len=3len=3 时就应保证
2.5 分情况考虑
我们考虑两种不同的情况
1. 普通串（如：[1,2,3,1,4,5][1,2,3,1,4,5][1,2,3,1,4,5] ），这种串是无法用repeat语句解决的，因此只能选择最小的输出数量进行输出
2. 可以循环的串（如：[1,2,1,2,1,2,1,2][1,2,1,2,1,2,1,2][1,2,1,2,1,2,1,2] ），这种串可以用repeat语句解决（相当于有循环节 [1,2][1,2][1,2] ），因此尝试选择循环节数量最少的进行循环（如为了输出 [1,2,1,2,1,2,1,2][1,2,1,2,1,2,1,2][1,2,1,2,1,2,1,2]，应该选择循环节数量为 4→[1,2]4 \rightarrow[1,2]4→[1,2] 而非循环节数量为 2→[1,2,1,2]2 \rightarrow[1,2,1,2]2→[1,2,1,2]）
那接下来我们想一下如何判断这个循环节是否存在呢？看第2.4部分
2.6 手动推导
2.7 边界测试
3 模型匹配
先提取关键词：时刻求取当前是否可行、区间
是 区间动态规划\huge{区间动态规划}区间动态规划
4 具体方案
4.1 动态规划定义（重点）
首先，先建立 dp 数组
设置 dpij{dp_i}_jdpi j 打印区间 [i,j][i,j][i,j] 范围内所需的最小print语句数量
4.2 初始化
都是 000
但是一格一定需要用一个print语句，因此对于每个 i(1≤i≤n)i (1 \le i \le n)i(1≤i≤n)，都要将 dpii{dp_i}_idpi i 设置为 111
4.3 状态转移方程
分两部分
* 先判断能否用repeat语句（特殊情况）的：
枚举循环节长度 kkk 从 [l,r+l−1][l,\sqrt{r+l-1}][l,r+l−1 ]（为了优化），每次检查 kkk 或者 (r+l−1)÷k(r + l - 1) \div k(r+l−1)÷k （优化所对应的额外检查） 是否为循环节，不是则进入普通情况，否则可以记录 dplr{dp_l}_rdpl r 为所有可能循环节长度 kkk 的 dpll+k−1{dp_l}_{l+k-1}dpl l+k−1 的最小值
* 一个是普通情况的：
枚举区间 [l,r][l,r][l,r] 之间的中间点 kkk，dplr{dp_l}_rdpl r 就是所有 dplk+dpk+1r{dp_l}_k+{dp_{k+1}}_rdpl k +dpk+1 r 中的最小值（大区间操作次数 === 最小小左区间操作次数+相对应最小右区间操作次数）
4.4 答案求取
检查 dp1n≤k{dp_1}_{n} \le kdp1 n ≤k 是否成立
5 最终代码（禁止抄袭，仅用于参考）
