影石Insta360杯 2025牛客暑期多校训练营10——[E] Sensei and Affection（使得数组趋同，所需要的最少区间+1操作数量。） · znzryb
## 题目大意
**使得数组趋同，所需要的最少区间加一操作数量。**
**题目描述**
给定 $n$ 个学生的初始好感度序列 $a_1, a_2, \dots, a_n$。
每天可以且必须进行一次操作：选择一个区间 $[l, r]$ ($1 \le l \le r \le n$)，将该区间内所有学生的好感度加 1（即对于所有 $l \le i \le r$，执行 $a_i := a_i + 1$）。
求使得最终序列中**最多**出现 $m$ 种不同数值所需的**最小操作次数**（最小天数）。
**输入描述**
第一行包含一个整数 $T$ ($1 \le T \le 10$)，表示测试数据组数。
对于每组测试数据：
第一行包含两个整数 $n, m$ ($1 \le n \le 400, 1 \le m \le 2$)，分别表示学生数量和允许的最大不同数值种数。
第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($0 \le a_i \le 100$)，表示初始好感度。
**输出描述**
对于每组测试数据，输出一行一个非负整数，表示所需的最小操作次数。
**样例**
```
输入
4
3 1
3 1 3
5 1
5 1 6 1 8
5 2
5 1 6 1 8
5 2
1 3 2 3 1
输出
2
12
3
1
```
**样例解释**
**第一组数据** ($n=3, m=1$)：
初始序列为 `[3, 1, 3]`，目标是让所有数字相同（最多 1 种数值）。
1. 选择区间 $[2, 2]$ 进行操作，序列变为 `[3, 2, 3]`。
1. 再次选择区间 $[2, 2]$ 进行操作，序列变为 `[3, 3, 3]`。
共需 2 次操作，序列中只有数值 3，满足条件。
**第三组数据** ($n=5, m=2$)：
初始序列为 `[5, 1, 6, 1, 8]`，目标是让序列中最多只有 2 种不同的数值。
最小需要 3 次操作。
## 思路讲解
首先我们注意到一件事情，就是这个 M 等于一或者 M 等于二。说白了要么变成同一个数，要么变成两个数。
我是这么感觉的，修改一个数，就是把所有的值修改为最大值。修改两个数其实也简单。修改两个数就是一个最大值，一个次大值，然后把其他的值都修改为次大值就好了。
上面就是我的感觉啊，我们先尝试一下，看看对不对。先尝试手磨一下样例。
不，手磨样例以后，我们发现把所有值修改为最大值，在只修改一个数的时候应该是对的。但是修改两个数的时候，这个情况就比较复杂了。修改两个数的话，我们之前的想法应该是错的。只有一个是对的，就是应该就是先要把这些数，其中的一些数肯定是要变为最大值的，其中的一些数肯定是要变为最大值的。但是至于**另外一个值需要怎样取**，就比较麻烦了。
::: AI 提示 1
看了下你的代码，你目前只写了平凡情况的判断。让我分步给你提示。
---
## 提示一：操作次数的计算公式
这是整道题的基础。假设目标数组是 $b$（满足 $b_i \ge a_i$），从 $a$ 变到 $b$ 的最少操作次数是多少？
令 $d_i = b_i - a_i \ge 0$（每个位置需要增加的量）。最少操作数 = **区间覆盖次数**，等于：
$$
d_1 + \sum_{i=2}^{n} \max(0,\ d_i - d_{i-1})
$$
这就是经典的"刷油漆"公式——每当 $d$ 序列往上爬一个台阶，就需要新开一批区间操作。
你可以先验证一下样例 1 和样例 2（$m=1$ 的情况）。
---
## 提示二：m=1 的情况
$m=1$ 时，所有值必须相同。由于只能增加，目标只能是 $v = \max(a)$。代入公式即可，$d_i = M - a_i$。
---
## 提示三：m=2 时，你的想法哪里有问题
你说"一个最大值，一个次大值"——**错在"次大值"**。
看样例 3：$a = [5, 1, 6, 1, 8]$，最优方案是把数组变成 $[8, 3, 8, 3, 8]$，两个值是 $8$ 和 $3$。但 $3$ 根本不在原始数组里！所以小的目标值不是"次大值"，而是需要**枚举**的。
---
## 提示四：m=2 的核心思路
**大的目标值一定是** $v = M = \max(a)$（因为原数组最大值的那个位置只能往上走，强制拉高这一组的目标，$v < M$ 不可能，$v > M$ 只会更贵）。
**小的目标值** $u$：枚举 $u$ 从 $0$ 到 $M-1$。对于每个固定的 $u$：
- $a_i > u$ 的位置：**强制**进大组（目标 $M$）；
- $a_i \le u$ 的位置：可以进小组（目标 $u$）或大组（目标 $M$），**用 DP 最优决定**。
---
## 提示五：DP 的定义
对于固定的 $u$，定义：
$$
dp[i][g] = \text{处理前 } i \text{ 个位置，第 } i \text{ 个位置属于第 } g \text{ 组时的最小操作数}
$$
- $g=0$：小组，$d_i = u - a_i$（仅当 $a_i \le u$）
- $g=1$：大组，$d_i = M - a_i$
转移：从 $(i-1, g')$ 到 $(i, g)$ 的代价是 $\max(0,\ d_i(g) - d_{i-1}(g'))$。
每个 $u$ 跑一次 $O(n)$ 的 DP，$u$ 最多枚举 $M \le 100$ 个值，总复杂度 $O(T \cdot M \cdot n)$，完全够用。
---
你可以用 $u=3$、样例 3 手跑一遍 DP 验证答案是 3，感受一下正确性。然后就可以动手实现了。
:::
OK 啊，偷偷看了一眼题解，这个题解写的还是可以的。比这垃圾 AI 提示写的好。这 AI 提示，我告诉他我的思路，我干脆比不告诉他我的思路还好，写的还好一点。这真的纯纯傻逼，还不如不写。
**M 等于一**的情况，一种比较方便的实现方法呢，就是**直接选择一个极长段**，这个极长段中的**所有数都比最大值小**。不断地选择这样的极长段进行操作，记录一下找不到这个这样子的极长段所需要的操作数量。说白了，这个做法就是一个贪心。
::: M = 2 的时候的错误解法（不过，这里面他这个段内逻辑求解写的还是非常好的，要可以参考参考。嗯，不是可以参考一下，是非常好，要参考）（这里面也有一些我画的图，因为前面我以为这个做法是正确的，不过呢，现在是现在发现是错的）
现在问题在于 M 等于2的情况下，另外一个值怎样取？但是你会发现，其实这道题目它的值域非常小啊，另外一个值怎样取？你**不知道怎样取**，你**直接枚举**就行了，一共就100个值，它总归是变成比最大值小的值，是吧？
OK 啊，我已经想到了一种可以解决 M 等于2的情况下的 DP 的方法。
不过这个方法目前的瓶颈在于，就是说从转移过来的位置到我的这个 pos 之间，这一段的求解，如果使用贪心法有点慢了。
我们现在的问题如下：
**对于段** $[l, r]$**，把它所有元素变成** $\max(a[l..r])$ **所需的最小操作数，如何快速预处理？**
（对于任意目标值 $T = \max(a[l..r]) + k$，代价只比 $T = \max$ 时多 $k$，而目标值 T 又不可能比 Max A 从 L 到 R 还小，这是不可能的。）
::: 进一步追问公式细节（\*\*讲的非常清楚非常清楚，好好看仔细看\*\*。）
好，从头推。
---
## 第一步：最少操作次数的一般公式
操作是"选一个连续区间，全体 +1"。目标是把 $a$ 变成 $b$（$b_i \ge a_i$）。
令 $d_i = b_i - a_i$，即每个位置还需要增加的量。问题变成：**用最少次"选连续区间全体 -1"操作，把** $d$ **清零。**
从左到右看 $d$ 数组：
- **位置** $l$**（最左）**：这里有 $d_l$ 层需求，必须有 $d_l$ 条操作从这里开始或经过。由于左边没有别的位置了，这 $d_l$ 条操作**全都必须从这里新起**。贡献 $d_l$。
- **位置** $i$**（**$i > l$**）**：从位置 $i-1$ 延伸过来的操作最多 $d_{i-1}$ 条。位置 $i$ 需要 $d_i$ 条操作覆盖。
- 若 $d_i \le d_{i-1}$：左边延过来的操作**绰绰有余**，多余的在 $i-1$ 和 $i$ 之间结束就行，不需要新开。贡献 $0$。
- 若 $d_i > d_{i-1}$：左边延过来的不够，还差 $d_i - d_{i-1}$ 条，**必须从位置** $i$ **新起**。贡献 $d_i - d_{i-1}$（贡献**即需要新开这么多条**）。
合起来：
$$
\text{操作数} = d_l + \sum_{i=l+1}^{r} \max(0,\ d_i - d_{i-1})
$$
---
## 第二步：代入目标值 = $mx$
令目标 $b_i = mx = \max(a[l..r])$，则 $d_i = mx - a_i$。
看差值：
$$
d_i - d_{i-1} = (mx - a_i) - (mx - a_{i-1}) = a_{i-1} - a_i
$$
$mx$ 抵消了。所以：
$$
\max(0,\ d_i - d_{i-1}) = \max(0,\ a_{i-1} - a_i)
$$
**这个东西跟** $mx$ **无关，只跟原数组相邻元素有关****。（这也是后续我们可以 O1 求的这个原因啊。）**
代回去：
$$
\text{cost}(l,r) = \underbrace{(mx - a_l)}_{\text{第一项}} + \sum{i=l+1}^{r}\max(0,\ a_{i-1} - a_i)
$$
---
## 第三步：前缀和预处理
定义：
$$
P[i] = \sum_{j=2}^{i}\max(0,\ a_{j-1} - a_j)
$$
则 $\sum_{i=l+1}^{r}\max(0, a_{i-1}-a_i) = P[r] - P[l]$。
最终：
$$
\text{cost}(l,r) = (mx[l][r] - a_l) + P[r] - P[l]
$$
---
这就是完整的推导过程。
:::
如果说我们画一张图具体来表达的话，就如下图：
:::
哎，上面的思路都被op4.6带歪了。我们应该让他先写一下这个程序，然后看看AC的以后，再写完这个顺序，发现他这个思路根本完全就是错的，提交上去以后，忘了以后，我仔细想一下，他这个思路完全是错的。嗯，当然也没有说错的那么明显，但是段间的这个逻辑不是很清楚，段间的这个逻辑是实际上是有问题的，段内的逻辑它的这个求解的逻辑是非常正确的，但是**段间的这个逻辑有问题**。
还有这个错误解法，还有一个问题就是反例，在M=二的情况下，最就是这两个值不一定就是一个最大值，就是这两个值中不一定包含最大值，即**最优解当中相同的这两个数不一定包含最大值**。
::: 反例\`\[0, 3, 0, 1\]\`，最优是\`\[1,4,1,1\]\`
你这个判断**直觉很强**，但结论确实不成立。
我不跟你抬杠，直接给你一个最小反例：
- 初始：`[0, 3, 0, 1]`
- `m = 2`
- `mx = 3`
如果强行要求答案值里包含 `3`，最优至少是 2 天。
例如变成 `[1,3,1,1]`（两值 `{1,3}`）：
- 需要增量 `d=[1,0,1,0]`
- 代价 `= d1 + Σmax(0,di-di-1) = 1+0+1+0 = 2`
但如果不包含 `3`，取两值 `{1,4}`，变成 `[1,4,1,1]`：
- 增量 `d=[1,1,1,0]`
- 代价 `= 1+0+0+0 = 1`
也就是：**把原来的最大值位置也抬高**，反而更优。
所以“`mx` 必须是最终两值之一”这个约束会 WA。
---
如果你仍然坚持“固定 `mx` 来写”，我可以按这个约束给你写一个版本，但我会明确标注：这是**受限解法**，不是题目的全局最优解。
:::
其实说白了这个判断，细想一下就是不对的，虽然最大值增加没有太大意义，但是如果说在有两个数的情况下，我去跨越它，去进行一些增加，也是有可能的。
::: AI （代码已经 AC）对 M = 2 思路的提示
可以，我把这版 DP 的核心讲清楚，尽量不绕。
## 1）先说为什么推翻原思路
你原来那版本质上是“分段 + 两个目标值”。问题不在“分段”，而在两个隐含假设：
- 把“大目标值”固定成 `mx`（全局最大初值）是错的。
反例就是你看到的：最优两值可能是 `{3,7}` 这类，不一定包含 `mx`。
- 段转移时容易把“段内代价”和“边界衔接代价”混在一起，公式很容易写错（你之前 `max(dp, cost)` 那个就是典型错位）。
所以我改成了“固定两目标值后，逐位置 DP”。
---
## 2）固定两目标值后的数学模型
假设最后只保留两个值：`low <= high`。
每个位置 `i` 只能选其中一个目标，且必须满足 `a[i] <= target`（只能加不能减）。
定义：
- 若位置 `i` 选了目标 `t_i`，则该位置需要增量 `d_i = t_i - a_i >= 0`。
把数组 `d` 造出来后，最少操作数是经典式子：
$$
\text{cost} = d_1 + \sum_{i=2}^{n}\max(0,\ d_i-d_{i-1})
$$
这个式子说明：代价只和相邻两位有关。
---
## 3）DP 状态与转移
设 `f[i][g]`：
- 处理到第 `i` 位；
- 第 `i` 位选的是第 `g` 个目标（`g=0` 表示 `low`，`g=1` 表示 `high`）；
- 的最小代价。
记：
- `tar(g) = (g==0 ? low : high)`
- `d(i,g) = tar(g) - a[i]`
初始化（`i=1`）：
- 若 `a[1] <= low`，`f[1][0] = low - a[1]`
- 若 `a[1] <= high`，`f[1][1] = high - a[1]`
转移（`i>=2`）：
从上一位状态 `pg` 转到 `g`：
$$
f[i][g] = \min\Big(f[i][g],\ f[i-1][pg] + \max(0,\ d(i,g)-d(i-1,pg))\Big)
$$
最终固定 `(low,high)` 的答案是：
$$
\min(f[n][0],f[n][1])
$$
---
## 4）外层枚举什么
- `a_i <= 100`，值域小，所以直接枚举 `low, high` 就行。
- 复杂度大约 `O(V^2 * n * 4)`，`V` 在 100 量级，`n<=400`，完全够。
---
如果你愿意，我下一条可以专门按你现在这份代码变量名，给你写“逐行对应解释”（哪一行是 `d_1`，哪一行是 `max(0, d_i-d_{i-1})`），这样你对照起来会最快。
:::
那么，他写的还是挺好的。嗯，思路其实很简单，就是在已知upper和已知lower的情况下，那么这个实际上可以使用一个 $O(n)$ 的DP就可以去解决这个问题。因为其实一个位置，他对答案的贡献只取决于他前面一个位置和它自己的这个位置，它取什么值。
这个下面就是已经知道了upper和lower以后，怎么样去DP的这个过程的代码。嗯，然后加粗高亮的地方呢，是有点问题。但是当时挖的地方，当时upper写成了max，然后这个DPI1呢，写成了DPI0。
[https://ac.nowcoder.com/acm/contest/view-submission?submissionId=82501084](https://ac.nowcoder.com/acm/contest/view-submission?submissionId=82501084)
我感觉想规避DPI1的错误，我们在这里取命只是为了让他不要比infinite高。那么我们直接命里面放一个INF就行了，不要写真实的东西，参有的时候会造成问题，不要写真实的东西，就写一个常数进去，就是**能用常数的地方就用常数**。
```cpp
vector<array<ll,2>> diff_arrays(N+2);
for (int i=1;i<=N;++i) {
if (A[i]<=lower) {
diff_arrays[i][0]=lower-A[i];
}
diff_arrays[i][1]=upper-A[i];
}
vector<array<ll,2>> dp(N+2,{INF,INF});
for (int i=1;i<=N;++i) {
if (i==1) {
if (A[i]<=lower) {
dp[i][0]=lower-A[i];
}
dp[i][1]=upper-A[i];
continue;
}
ll add01=INF,add00=INF;
if (A[i-1]<=lower) {
add01=max(0ll,diff_arrays[i][1]-diff_arrays[i-1][0]);
if (A[i]<=lower) {
add00=max(0ll,diff_arrays[i][0]-diff_arrays[i-1][0]);
}
}
ll add10=INF,add11=INF;
if (A[i]<=lower) {
add10=max(0ll,diff_arrays[i][0]-diff_arrays[i-1][1]);
}
add11=max(0ll,diff_arrays[i][1]-diff_arrays[i-1][1]);
dp[i][0]=min({dp[i][0],dp[i-1][0]+add00,dp[i-1][1]+add10});
dp[i][1]=min({dp[i][1],dp[i-1][0]+add01,dp[i-1][1]+add11});
}
```
## AC代码
AC
[https://ac.nowcoder.com/acm/contest/view-submission?submissionId=82503145](https://ac.nowcoder.com/acm/contest/view-submission?submissionId=82503145)
::: 源代码
```cpp
/**
* Problem: Sensei and Affection (affection)
* Contest:
* Judge: NowCoder
* URL: https://ac.nowcoder.com/acm/contest/108307/E
* Created: 2026-02-22 20:44:42
* Author: Gospel_rock
* My blog: https://znzryb.com/
*
* Powered by AutoCp https://github.com/Pushpavel/AutoCp
*/
#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define debug(var) cerr << #var <<" = ["<<var<<"]"<<"\n";
#define debug1d(a) \
cerr << #a << " = ["; \
for (int i = 0; i < (int)(a).size(); i++) \
cerr << (i ? ", " : "") << a[i]; \
cerr << "]\n";
#define debug2d(a) \
cerr << #a << " = [\n"; \
for (int i = 0; i < (int)(a).size(); i++) \
{ \
cerr << " ["; \
for (int j = 0; j < (int)(a[i]).size(); j++) \
cerr << (j ? ", " : "") << a[i][j]; \
cerr << "]\n"; \
} \
cerr << "]\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)
using namespace std;
using ll = long long;
using ull = unsigned long long;
using DB = double;
// using i128 = __int128;
using CD = complex<double>;
static constexpr ll MAXN = (ll)1e6+10, INF = (1ll<<61)-1;
static constexpr ll mod = 998244353; // (ll)1e9+7;
static constexpr double eps = 1e-8;
const double pi = acos(-1.0);
ll lT,testcase;
/*
*
*/
void Solve() {
ll N,M;
cin >> N >> M;
vector<ll> A(N+2);
for (int i=1;i<=N;++i) {
cin>>A[i];
}
ll mx=*max_element(all(A));
ll mn=*min_element(A.begin()+1,A.begin()+N+1);
set<ll> st;
for (int i=1;i<=N;++i) {
st.insert(A[i]);
}
if (SZ(st)<=M) {
cout<<0<<"\n";
return;
}
if (M==1) {
ll ans=0;
// A[0]=INF;
while (true) {
bool finded=false;
ll up=-1;
for (int i=1;i<=N;++i) {
if (A[i]<mx) {
finded=true;
A[i]++;
if (i-1!=up) {
++ans;
}
up=i;
}
}
if (!finded) {
break;
}
}
cout<<ans<<"\n";
}else {
ll ans=INF;
// 这里的逻辑应该就是直接去枚举lower和upper
for (ll lower=mn;lower<=100;++lower) {
for (ll upper=mx;upper<=200;++upper) {
vector<array<ll,2>> diff_arrays(N+2);
for (int i=1;i<=N;++i) {
if (A[i]<=lower) {
diff_arrays[i][0]=lower-A[i];
}
diff_arrays[i][1]=upper-A[i];
}
vector<array<ll,2>> dp(N+2,{INF,INF});
for (int i=1;i<=N;++i) {
if (i==1) {
if (A[i]<=lower) {
dp[i][0]=lower-A[i];
}
dp[i][1]=upper-A[i];
continue;
}
ll add01=INF,add00=INF;
if (A[i-1]<=lower) {
add01=max(0ll,diff_arrays[i][1]-diff_arrays[i-1][0]);
if (A[i]<=lower) {
add00=max(0ll,diff_arrays[i][0]-diff_arrays[i-1][0]);
}
}
ll add10=INF,add11=INF;
if (A[i]<=lower) {
add10=max(0ll,diff_arrays[i][0]-diff_arrays[i-1][1]);
}
add11=max(0ll,diff_arrays[i][1]-diff_arrays[i-1][1]);
dp[i][0]=min({dp[i][0],dp[i-1][0]+add00,dp[i-1][1]+add10});
dp[i][1]=min({dp[i][1],dp[i-1][0]+add01,dp[i-1][1]+add11});
}
ll lans=min(dp[N][0],dp[N][1]);
ans=min(lans,ans);
// #ifdef LOCAL
// if (lans==0) {
// debug(lower);debug(upper);
// debug2d(dp);
// }
// #endif
}
}
cout<<ans<<"\n";
}
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
#ifdef LOCAL
cout.setf(ios::unitbuf); // 无缓冲流，方便我们调试
#endif
cin >> lT;
for (testcase = 1; testcase <= lT; ++testcase)
Solve();
return 0;
}
/*
AC
https://ac.nowcoder.com/acm/contest/view-submission?submissionId=82503145
1
5 2
5 1 6 1 8
1
5 2
1 3 2 3 1
*/
```
:::
::: 数据生成器
```cpp
/**
* Problem: Sensei and Affection (affection)
* Contest:
* Judge: NowCoder
* URL: https://ac.nowcoder.com/acm/contest/108307/E
* Created: 2026-02-22 21:38:47
* Author: Gospel_rock
* My blog: https://znzryb.com/
*
* Powered by AutoCp https://github.com/Pushpavel/AutoCp
*/
#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define debug(var) cerr << #var <<" = ["<<var<<"]"<<"\n";
#define debug1d(a) \
cerr << #a << " = ["; \
for (int i = 0; i < (int)(a).size(); i++) \
cerr << (i ? ", " : "") << a[i]; \
cerr << "]\n";
#define debug2d(a) \
cerr << #a << " = [\n"; \
for (int i = 0; i < (int)(a).size(); i++) \
{ \
cerr << " ["; \
for (int j = 0; j < (int)(a[i]).size(); j++) \
cerr << (j ? ", " : "") << a[i][j]; \
cerr << "]\n"; \
} \
cerr << "]\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)
using namespace std;
using ll = long long;
using ull = unsigned long long;
using DB = double;
// using i128 = __int128;
using CD = complex<double>;
static constexpr ll MAXN = (ll)1e6+10, INF = (1ll<<61)-1;
static constexpr ll mod = 998244353; // (ll)1e9+7;
static constexpr double eps = 1e-8;
const double pi = acos(-1.0);
ll lT,testcase;
/*
*
*/
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
void Solve() {
cout<<1<<"\n";
ll N=uniform_int_distribution<ll>(1,7)(rng),M=2;
cout<<N<<" "<<M<<"\n";
for (int i=1;i<=N;++i) {
cout<<uniform_int_distribution<ll>(0,7)(rng)<<" ";
}
cout<<"\n";
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
#ifdef LOCAL
cout.setf(ios::unitbuf); // 无缓冲流，方便我们调试
#endif
// cin >> lT;
// for (testcase=1;testcase<=lT;++testcase)
Solve();
return 0;
}
/*
*/
```
:::
::: 暴力程序（bfs，暴力直接采用A数组作为状态，记忆化BFS）
```cpp
/**
* Problem: Sensei and Affection (affection)
* Contest:
* Judge: NowCoder
* URL: https://ac.nowcoder.com/acm/contest/108307/E
* Created: 2026-02-22 21:22:12
* Author: Gospel_rock
* My blog: https://znzryb.com/
*
* Powered by AutoCp https://github.com/Pushpavel/AutoCp
*/
#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define debug(var) cerr << #var <<" = ["<<var<<"]"<<"\n";
#define debug1d(a) \
cerr << #a << " = ["; \
for (int i = 0; i < (int)(a).size(); i++) \
cerr << (i ? ", " : "") << a[i]; \
cerr << "]\n";
#define debug2d(a) \
cerr << #a << " = [\n"; \
for (int i = 0; i < (int)(a).size(); i++) \
{ \
cerr << " ["; \
for (int j = 0; j < (int)(a[i]).size(); j++) \
cerr << (j ? ", " : "") << a[i][j]; \
cerr << "]\n"; \
} \
cerr << "]\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)
using namespace std;
using ll = long long;
using ull = unsigned long long;
using DB = double;
// using i128 = __int128;
using CD = complex<double>;
static constexpr ll MAXN = (ll)1e6+10, INF = (1ll<<61)-1;
static constexpr ll mod = 998244353; // (ll)1e9+7;
static constexpr double eps = 1e-8;
const double pi = acos(-1.0);
ll lT,testcase;
/*
*
*/
struct Status {
vector<ll> A;
ll step;
};
void Solve() {
ll N,M;
cin >> N >> M;
vector<ll> A(N+2);
for (int i=1;i<=N;++i) {
cin>>A[i];
}
queue<Status> q;
q.push({A,0});
set<vector<ll>> a_memo_st;
a_memo_st.insert(A);
auto check=[&](const vector<ll> &a) {
set<ll> st;
for (int i=1;i<=N;++i) {
st.insert(a[i]);
}
return SZ(st)<=M;
};
while (!q.empty()) {
auto [a,step]=q.front();
q.pop();
if (check(a)) {
cout<<step<<"\n";
return;
}
for (int l=1;l<=N;++l) {
for (int r=l;r<=N;++r) {
vector<ll> opa=a;
for (int i=l;i<=r;++i) {
opa[i]++;
}
if (!a_memo_st.contains(opa)) {
a_memo_st.insert(opa);
q.push({opa,step+1});
}
}
}
}
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
#ifdef LOCAL
cout.setf(ios::unitbuf); // 无缓冲流，方便我们调试
#endif
cin >> lT;
for (testcase=1;testcase<=lT;++testcase)
Solve();
return 0;
}
/*
3
3 1
3 1 3
5 2
5 1 6 1 8
5 2
1 3 2 3 1
*/
```
:::
## 心路历程（WA，TLE，MLE……）
::: AI 纠错 2
我理解你的想法了——你在枚举"段的边界"，然后对每一段内部用贪心求代价，这样确实是 $O(n^2)$ 甚至更高。
但其实**完全不需要"分段"的思维**。
---
## 关键观察：操作数公式是逐位累加的
回顾代价公式：
$$
\text{cost} = d_1 + \sum_{i=2}^{n} \max(0,\ d_i - d_{i-1})
$$
这个公式里，每一项 $\max(0, d_i - d_{i-1})$ 只和**相邻两个位置**的 $d$ 值有关，和更远的位置无关。
所以 DP **不需要跳跃，直接逐位转移即可**，每步转移 $O(1)$。
---
## 正确的 DP 定义
对于固定的小目标值 $u$（外层枚举），令：
- $d_i(0) = u - a_i$（位置 $i$ 分配到小组，仅当 $a_i \le u$）
- $d_i(1) = M - a_i$（位置 $i$ 分配到大组）
定义：
$$
dp[i][g] = \text{处理完前 } i \text{ 个位置、第 } i \text{ 个位置属于第 } g \text{ 组时的最小总操作数}
$$
**转移**（每步 $O(1)$，无需关心段的内部）：
$$
dp[i][g] = \min_{g' \in \{0,1\}} \left( dp[i-1][g'] + \max\left(0,\ d_i(g) - d_{i-1}(g')\right) \right)
$$
- 这里 $d_{i-1}(g')$ 就是上一个位置在 $g'$ 组时的 $d$ 值，是常数，查表即可。
- 每个转移只需要做一次 $\max$ 和一次 $\min$，$O(1)$。
**初始化**：$dp[1][0] = d_1(0)$（若 $a_1 \le u$），$dp[1][1] = d_1(1)$。
**答案**：$\min(dp[n][0], dp[n][1])$。
---
## 总复杂度
| 层次 | 复杂度 |
| --- | --- |
| 枚举 $u$（0 到 $M \le 100$） | $O(M)$ |
| 每个 $u$ 跑一遍 DP | $O(n)$ |
| **总计** | $O(M \cdot n) \approx O(100 \times 400)$ |
远远够用，不需要任何段内贪心。
---
你之前思路里的"段"其实并不是必要的抽象——相邻两位之间的 $\max(0, d_i - d_{i-1})$ 本身就已经捕捉了所有段的边界信息，DP 直接逐位推进即可。
:::
::: AI 纠错 3
选第二条路，在你的思路上解决。
---
## 你的 DP 定义
`dp[pos][g]` = 前 pos 个位置处理完毕、**最后一段（以 pos 结尾的连续段）属于第 g 组**时的最小操作数。
转移从所有 `prev`（0 到 pos-1）来，段 `[prev+1, pos]` 全部是第 g 组。
---
## 段代价的拆解
对于段 `[prev+1, pos]` 全在 g 组（目标值 $t_g$ 为 $u$ 或 $M$），它对总操作数的贡献分两部分：
**① 边界项**（连接前一段和本段，O(1)）：
$$
\max\!\left(0,\ t_g - a_{prev+1} - (t_{g'} - a_{prev})\right)
$$
**② 段内部项**：
$$
\sum_{i=prev+2}^{pos} \max(0,\ d_i^{(g)} - d_{i-1}^{(g)}) = \sum_{i=prev+2}^{pos}\max(0,\ a_{i-1} - a_i)
$$
**关键：这个内部项与** $t_g$**（即** $u$ **还是** $M$**）完全无关！** 可以预处理前缀和：
$$
P[i] = \sum_{j=2}^{i} \max(0,\ a_{j-1} - a_j)
$$
则段内部项 = $P[pos] - P[prev+1]$，**O(1) 查询**。
---
## 转移公式
$$
dp[pos][g] = \min_{\substack{prev \in [0, pos-1] \\ g' \in \{0,1\}}} \left(\ dp[prev][g'] + \underbrace{\max(0,\ t_g - a_{prev+1} - t_{g'} + a_{prev})}{\text{边界项，O(1)}} + \underbrace{P[pos] - P[prev+1]}{\text{内部项，O(1)}}\ \right)
$$
特殊地，`prev=0` 时边界项 = $t_g - a_1$（无前一段，$d_0 = 0$）。
---
## 复杂度
- 枚举 $u$：$O(M) = O(100)$
- 每个 $u$，枚举 pos 和 prev：$O(n^2) = O(160000)$
- 合计：$O(M \cdot n^2) \approx 1.6 \times 10^7$，完全够用
---
一句话总结：**预处理前缀和** $P[i]$**，段内部项变 O(1) 查询，转移总体 O(n²)，搞定。**
:::
这两个 AI 回答都写的比较招笑，我们再看一看它有没有更好的回答。
::: AI 的回答（不小心换成 Sonnet 4\.6了。我想它前面的和这个回答怎么都这么招笑啊？OPUS 4\.6和 Sonnet 4\.6搞混了，绷不住了。）
## 答案
**预处理前缀和**，令：
$$
P[i] = \sum_{j=2}^{i} \max(0,\ a[j-1] - a[j])
$$
（O(n) 预处理，O(1) 查询）
**预处理区间最大值**：
$$
mx[l][r] = \max(a[l],\ldots,a[r])
$$
（O(n²) 预处理所有对）
---
## 公式
$$
\text{cost}(l, r) = \bigl(mx[l][r] - a[l]\bigr) + P[r] - P[l]
$$
**推导**：令 $d_i = mx[l][r] - a[i]$，代入操作数公式：
$$
d_l + \sum_{i=l+1}^{r} \max(0, d_i - d_{i-1}) = (mx - a[l]) + \sum_{i=l+1}^{r}\max(0,\ a[i-1]-a[i]) = (mx - a[l]) + P[r] - P[l]
$$
---
## 平移性质
目标值变为 $mx[l][r] + k$，代价恰好增加 $k$（因为 $d_l$ 增加 $k$，内部差值不变）：
$$
\text{cost}(l, r, \text{target} = mx + k) = \text{cost}(l, r) + k
$$
---
## 验证
$a = [5,1,6,1,8]$，$P = [0, 4, 4, 9, 9]$，整段 $[1,5]$：$mx=8$，$\text{cost} = (8-5) + 9 - 0 = 12$ ✓
:::