P16738 [GKS 2019 #F] Flattening

Blotch 砌了一面墙。这面墙由 $N$ 段组成，从左到右编号为 $1$ 到 $N$。由于他当时匆忙砌墙，并非所有段的高度都相同。第 $i$ 段墙的高度为 $A_i$ 米。 Blotch 希望通过重建其中的一些段来修复他的墙。他可以将每一段重建的高度设为任意他想要的高度。 如果满足 $A_i \ne A_{i+1}$ 的下标 $i$（$1 \le i < N$）的个数不超过 $K$，那么 Blotch 就会感到满意。 请问 Blotch 至少需要重建多少段墙，才能使他感到满意？

输入的第一行给出测试用例的数量 $T$。接下来有 $T$ 个测试用例。每个测试用例的第一行包含两个整数 $N$ 和 $K$，分别表示墙的段数和相邻段之间高度变化的最大允许次数。 第二行包含 $N$ 个整数。其中第 $i$ 个整数是 $A_i$，表示第 $i$ 段墙的高度。

对于每个测试用例，输出一行，格式为 `Case #x: y`，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是 Blotch 为了感到满意而需要重建的最少段数。

在第一个样例中，墙有 $N = 8$ 段，如果相邻段之间高度变化的次数不超过 $K = 2$，Blotch 就会满意。他可以： - 将第 $2$ 段重建为高度 $300$， - 将第 $6$ 段重建为高度 $200$， - 将第 $8$ 段重建为高度 $800$。 这样得到的高度序列为 $300, 300, 300, 300, 200, 200, 800, 800$，使 Blotch 感到满意。 在第二个样例中，墙有 $N = 5$ 段，Blotch 在相邻段高度变化不超过 $K = 3$ 时就会满意。他原本的墙已经满足条件，因此不需要重建任何段。 在第三个样例中，墙有 $N = 7$ 段，Blotch 在相邻段高度变化不超过 $K = 3$ 时就会满意。他可以： - 将第 $2$ 段重建为高度 $10$。 得到的高度序列为 $10, 10, 40, 10, 10, 30, 30$，使 Blotch 感到满意。 在第四个样例中，墙有 $N = 10$ 段，Blotch 在相邻段高度变化不超过 $K = 2$ 时就会满意。他可以： - 将第 $5$ 段重建为高度 $60$， - 将第 $6$ 段重建为高度 $60$。 得到的高度序列为 $30, 30, 60, 60, 60, 60, 60, 60, 30, 30$，使 Blotch 感到满意。 ### 限制条件 $1 \le T \le 100$。 对于所有 $i$，$1 \le A_i \le 1000$。 $0 \le K \le N$。 **测试集 1（可见）** $2 \le N \le 20$。 **测试集 2（隐藏）** $2 \le N \le 100$。 翻译由 DeepSeek V4 Pro 完成