P16875 [GKS 2022 #B] Unlock the Padlock

假设你有一个密码锁，它由 $N$ 个拨盘组成，初始时设置为随机组合。密码锁的拨盘大小为 $D$，即每个拨盘的值可以是 $0$ 到 $D-1$（包含两端），并且可以向上或向下旋转。拨盘从左到右排列，最左和最右的位置分别为 $1$ 和 $N$。将所有的拨盘值设为 $0$ 即可打开密码锁。 你可以执行零次或多次以下操作： - 选择任意区间 $[l, r]$，满足 $1 \le l \le r \le N$，并将该区间内的所有拨盘同时向上或向下旋转。向上旋转会使区间 $[l, r]$ 中每个拨盘的值增加 $1$，向下旋转则减少 $1$。注意，值为 $D-1$ 的拨盘向上旋转后会变成 $0$，值为 $0$ 的拨盘向下旋转后会变成 $D-1$。 操作序列必须满足以下条件： - 第 $i-1$ 次操作选择的区间 $[l_{i-1}, r_{i-1}]$ 必须完全包含在第 $i$ 次操作选择的区间 $[l_i, r_i]$ 之内，即 $l_i \le l_{i-1} \le r_{i-1} \le r_i$。第一次操作 $([l_1, r_1])$ 可以任意选择。 解锁初始组合为 $[1, 1, 2, 2, 3, 3]$ 的密码锁的有效操作序列示例： 1. 将区间 $[5, 6]$ 向下旋转。 2. 将区间 $[3, 6]$ 向下旋转。 3. 将区间 $[1, 6]$ 向下旋转。 以下是一些不能执行的操作： 1. 在 $[6, 9]$ 之后旋转 $[1, 4]$，因为 $[6, 9]$ 没有完全包含在 $[1, 4]$ 中（不满足 $r_{i-1} \le r_i$，其中 $r_{i-1}=9$，$r_i=4$）。 2. 在 $[2, 7]$ 之后旋转 $[3, 6]$。 你的目标是输出使密码锁所有拨盘归零所需的**最少**有效操作次数。

输入的第一行包含测试用例的数量 $T$。接下来有 $T$ 个测试用例。 每个测试用例由 $2$ 行组成。 每个测试用例的第一行包含 $2$ 个整数 $N$ 和 $D$，分别表示密码锁的拨盘数量和拨盘的大小。 每个测试用例的第二行包含 $N$ 个整数 $V_1, V_2, \ldots, V_N$，其中第 $i$ 个整数表示初始组合中第 $i$ 个拨盘的值。

对于每个测试用例，输出一行，格式为 `Case #x: y`，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是解锁密码锁所需的最少操作次数。

在样例 #1 中，解锁密码锁所需的最少操作次数为 $3$。可以使用以下操作解锁： 1. 将区间 $[4, 4]$ 向下旋转。 2. 将区间 $[3, 5]$ 向下旋转。 3. 将区间 $[1, 6]$ 向下旋转。 在样例 #2 中，解锁密码锁所需的最少操作次数为 $2$。可以使用以下操作解锁： 1. 将区间 $[3, 4]$ 向上旋转。 2. 将区间 $[2, 6]$ 向下旋转。 ### 限制条件 $1 \le T \le 100$。 对于所有 $i$，$0 \le V_i \le D - 1$。 **测试集 1** $1 \le N \le 40$。 $D = 2$。 **测试集 2** $1 \le N \le 40$。 $2 \le D \le 10$。 **测试集 3** $1 \le N \le 400$。 $2 \le D \le 10^9$。 翻译由 DeepSeek V4 Pro 完成