洛谷 P11838 分析（别看）

科技起源

2026-07-08 11:15:26

发布于：河北

1阅读

0回复

0点赞

原题链接

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 大拆小、小组大

2.2 正向思维转逆向思维，逆向思维转正向思维

2.3 以终为始、以始为终

2.4 数学

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

序列（题目中已经给出） $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$ 时就应保证

2.5 分情况考虑

我们考虑两种不同的情况

普通串（如： $[1,2,3,1,4,5]$ ），这种串是无法用repeat语句解决的，因此只能选择最小的输出数量进行输出
可以循环的串（如： $[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.4部分

2.6 手动推导

2.7 边界测试

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