影石Insta360杯 2025牛客暑期多校训练营10——[E] Sensei and Affection（使得数组趋同，所需要的最少区间+1操作数量。）

题目大意

使得数组趋同，所需要的最少区间加一操作数量。

题目描述

给定 $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]。

2. 再次选择区间 $[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]$$

---

这就是完整的推导过程。

</div>

如果说我们画一张图具体来表达的话，就如下图：

哎，上面的思路都被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

我感觉想规避DPI1的错误，我们在这里取命只是为了让他不要比infinite高。那么我们直接命里面放一个INF就行了，不要写真实的东西，参有的时候会造成问题，不要写真实的东西，就写一个常数进去，就是能用常数的地方就用常数。

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

源代码

/**
 * 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

*/

数据生成器

/**
 * 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）

/**
 * 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$ ✓

# 贪心 greedy # 差分 diff # dp # 最优化 optimization

影石Insta360杯-2025牛客暑期多校训练营10 原——[F] Sensei and Yuuka Going Shopping

ABC-419-E - Subarray Sum Divisibility（len连续段和都是M倍数的所需最少操作数，操作是让一个元素增加1）