「USACO 2019.1 Platinum」Redistricting

zhoujinchong2004 @ 2025-10-27 17:01:10

一、问题分析

1.1 题目理解

给定 $N$ 块牧草地组成的序列，每块牧草地上有一头奶牛（H表示荷斯坦牛，G表示更赛牛）。需要将序列划分为若干个连续的区，满足：

每个区至多包含 $K$ 块牧草地
每块牧草地恰好属于一个区
最小化"更赛牛较多或均势"的区的数量

1.2 问题转化

对于一个区间 $[j+1, i]$ ，判断是否为"更赛牛较多或均势"：

更赛牛数量 $\geq$ 荷斯坦牛数量

我们可以将问题转化：

令 G 字符的贡献为 $+1$
令 H 字符的贡献为 $-1$
定义前缀和 $g[i] = g[i-1] + (s[i] == 'G' ? 1 : -1)$

则区间 $[j+1, i]$ 是"更赛牛较多或均势"当且仅当：

g[i] - g[j] \geq 0

1.3 前缀和转化的严格证明

定理1.1（前缀和等价性）：对于区间 $[j+1, i]$ （ $1 \leq j+1 \leq i \leq N$ ），设该区间内更赛牛的数量为 $G_{[j+1,i]}$ ，荷斯坦牛的数量为 $H_{[j+1,i]}$ ，则：

$$G_{[j+1,i]} \geq H_{[j+1,i]} \iff g[i] - g[j] \geq 0 $$

证明：

定义指示函数：

$$\delta(k) = \begin{cases} 1 & \text{if } s[k] = 'G' \\ -1 & \text{if } s[k] = 'H' \end{cases} $$

则前缀和定义为：

g[i] = \sum_{k=1}^{i} \delta(k), \quad g[0] = 0

区间 $[j+1, i]$ 的前缀和差为：

$$\begin{aligned} g[i] - g[j] &= \sum_{k=1}^{i} \delta(k) - \sum_{k=1}^{j} \delta(k) \\ &= \sum_{k=j+1}^{i} \delta(k) \\ &= \sum_{k=j+1}^{i} \mathbb{1}_{[s[k]='G']} - \sum_{k=j+1}^{i} \mathbb{1}_{[s[k]='H']} \\ &= G_{[j+1,i]} - H_{[j+1,i]} \end{aligned}$$

其中 $\mathbb{1}_{[P]}$ 是示性函数。

因此：

$$g[i] - g[j] \geq 0 \iff G_{[j+1,i]} - H_{[j+1,i]} \geq 0 \iff G_{[j+1,i]} \geq H_{[j+1,i]} $$

定理得证。

推论1.1：区间 $[j+1, i]$ 是"更赛牛较多或均势"当且仅当 $g[i] - g[j] \geq 0$ 。

二、算法设计

2.1 动态规划状态定义

定义 $f[i]$ 表示处理前 $i$ 个位置时，更赛牛较多或均势的区的最小数量。

定义2.1（合法划分）：对于前 $i$ 个位置，一个划分 $\mathcal{P} = \{I_1, I_2, \ldots, I_m\}$ 是合法的，当且仅当：

$I_k = [a_k, b_k]$ 都是连续区间，其中 $1 \leq a_k \leq b_k \leq i$
$\bigcup_{k=1}^{m} I_k = \{1, 2, \ldots, i\}$ （覆盖所有位置）
$I_k \cap I_\ell = \emptyset$ 对于 $k \neq \ell$ （无重叠）
$|I_k| \leq K$ 对于所有 $k$ （区间长度限制）
$b_1 < a_2$ , $b_2 < a_3$ , ..., $b_{m-1} < a_m$ （按顺序排列）

定义2.2（划分代价）：对于一个合法划分 $\mathcal{P}$ ，定义其代价为"更赛牛较多或均势"的区间数：

$$\text{cost}(\mathcal{P}) = \sum_{I \in \mathcal{P}} \mathbb{1}_{[I \text{ 是更赛牛较多或均势}]} $$

定理2.1（状态定义正确性）： $f[i]$ 等于所有前 $i$ 个位置的合法划分中的最小代价：

$$f[i] = \min_{\mathcal{P} \text{ 是合法划分}} \text{cost}(\mathcal{P}) $$

2.2 状态转移方程

考虑第 $i$ 个位置，它必须属于某个区间。设这个区间为 $[j+1, i]$ ，则：

区间长度限制： $1 \leq i - j \leq K$ ，即 $\max(0, i - K) \leq j < i$
转移方程：

$$f[i] = \min_{\max(0,i-K) \leq j < i} \left\{ f[j] + \begin{cases} 1 & \text{if } g[i] - g[j] \geq 0 \\ 0 & \text{otherwise} \end{cases} \right\} $$

简写为：

f[i] = \min_{\max(0,i-K) \leq j < i} C(i, j)

其中 $C(i, j) = f[j] + \mathbb{1}_{[g[i] - g[j] \geq 0]}$ 。

定理2.2（状态转移方程正确性）：上述转移方程正确计算 $f[i]$ 。

证明：

（⇒）首先证明 $f[i]$ 不大于任何合法划分的代价。

设 $\mathcal{P}$ 是前 $i$ 个位置的任意合法划分，设最后一个区间为 $I_m = [j+1, i]$ 。则：

由区间长度限制， $|I_m| = i - j \leq K$ ，即 $j \geq i - K$
由于 $I_m$ 包含位置 $i$ ，所以 $j < i$
因此 $\max(0, i-K) \leq j < i$

设前 $j$ 个位置的划分为 $\mathcal{P}' = \{I_1, \ldots, I_{m-1}\}$ ，则：

$$\text{cost}(\mathcal{P}) = \text{cost}(\mathcal{P}') + \mathbb{1}_{[I_m \text{ 是更赛牛较多或均势}]} $$

由 $f[j]$ 的定义， $f[j] \leq \text{cost}(\mathcal{P}')$ ，因此：

$$\text{cost}(\mathcal{P}) \geq f[j] + \mathbb{1}_{[g[i]-g[j] \geq 0]} = C(i, j) $$

由于这对任意合法的 $j$ 都成立，所以：

$$\text{cost}(\mathcal{P}) \geq \min_{\max(0,i-K) \leq j < i} C(i, j) $$

（⇐）然后证明存在一个合法划分达到这个下界。

设 $j^* = \arg\min_{\max(0,i-K) \leq j < i} C(i, j)$ 。由归纳假设，存在前 $j^*$ 个位置的最优划分 $\mathcal{P}^*$ 使得 $\text{cost}(\mathcal{P}^*) = f[j^*]$ 。

构造前 $i$ 个位置的划分 $\mathcal{P} = \mathcal{P}^* \cup \{[j^*+1, i]\}$ ，则：

$$\text{cost}(\mathcal{P}) = f[j^*] + \mathbb{1}_{[g[i]-g[j^*] \geq 0]} = C(i, j^*) = \min_{\max(0,i-K) \leq j < i} C(i, j) $$

因此转移方程正确。

2.3 初始状态

$f[0] = 0$ （没有任何区间）

命题2.1（初始状态正确性）：空序列的唯一合法划分是空划分，其代价为0。

2.4 边界条件与完备性

定理2.3（问题可解性）：对于任意 $1 \leq i \leq N$ ，至少存在一个 $j$ 使得 $\max(0, i-K) \leq j < i$ 。

证明：

由于 $K \geq 1$ （题目保证），所以：

如果 $i \geq 1$ ，则 $j = i - 1$ 满足 $j < i$ 且 $j \geq \max(0, i-K)$

因此转移方程总是有定义的。

推论2.1：当 $K \geq N$ 时，可以将整个序列划分为一个区间，问题总是有解的。

2.5 朴素算法时间复杂度分析

朴素的DP转移时间复杂度为 $O(NK)$ ，对于 $N = 3 \times 10^5$ 和 $K = N$ 的情况，复杂度可达 $O(N^2) = O(9 \times 10^{10})$ ，会超时，需要优化。

三、单调队列优化

3.1 优化思路

观察状态转移方程，我们需要在区间 $[i-K, i-1]$ 中找到使 $f[j] + [g[i] - g[j] \geq 0]$ 最小的 $j$ 。

关键观察：

固定 $i$ 时， $g[i]$ 是常数
对于两个决策点 $j_1 < j_2$ ，如果 $j_1$ 始终不如 $j_2$ 优，则 $j_1$ 可以被淘汰

3.2 单调队列维护策略

维护一个单调队列，队列中存储的是可能成为最优决策的 $j$ 值。

入队策略：对于新的位置 $i$ ，将其加入队列前：

从队尾删除所有"不如 $i$ 优"的元素
比较标准：
- 如果 $f[i] < f[q[\text{tail}-1]]$ ，则 $q[\text{tail}-1]$ 可以删除
- 如果 $f[i] = f[q[\text{tail}-1]]$ 且 $g[i] > g[q[\text{tail}-1]]$ ，则 $q[\text{tail}-1]$ 也可以删除

出队策略：超出范围 $[i-K, i-1]$ 的元素从队头删除。

决策选择：队头元素即为最优决策。

3.3 严格数学证明

3.3.1 问题的数学形式化

定义3.1（代价函数）：对于决策点 $j$ 和当前位置 $i$ ，定义代价函数：

$$C(i, j) = f[j] + \mathbb{1}_{[g[i] - g[j] \geq 0]} $$

其中 $\mathbb{1}_{[P]}$ 是示性函数：

$$\mathbb{1}_{[P]} = \begin{cases} 1 & \text{if } P \text{ is true} \\ 0 & \text{if } P \text{ is false} \end{cases} $$

定义3.2（决策优劣关系）：对于两个决策点 $j_1, j_2$ 和位置 $i$ ，称 $j_2$ 不劣于 $j_1$ （记为 $j_2 \preceq_{i} j_1$ ），当且仅当：

C(i, j_2) \leq C(i, j_1)

称 $j_2$ 严格优于 $j_1$ （记为 $j_2 \prec_{i} j_1$ ），当且仅当：

C(i, j_2) < C(i, j_1)

3.3.2 决策支配性引理

引理3.1（决策支配性）：设 $j_1 < j_2$ 是两个决策点。若满足以下条件之一：

$f[j_1] > f[j_2]$
$f[j_1] = f[j_2]$ 且 $g[j_1] \leq g[j_2]$

则对于任意 $i > j_2$ ，都有 $j_2 \preceq_{i} j_1$ （即 $j_2$ 不劣于 $j_1$ ）。

证明：

我们分两种情况讨论。

情况1： $f[j_1] > f[j_2]$

此时 $f[j_1] \geq f[j_2] + 1$ （因为 $f$ 值均为非负整数）。

对于任意 $i > j_2$ ，代价函数的差值为：

$$\begin{aligned} C(i, j_1) - C(i, j_2) &= \left(f[j_1] + \mathbb{1}_{[g[i] - g[j_1] \geq 0]}\right) - \left(f[j_2] + \mathbb{1}_{[g[i] - g[j_2] \geq 0]}\right) \\ &= (f[j_1] - f[j_2]) + \left(\mathbb{1}_{[g[i] - g[j_1] \geq 0]} - \mathbb{1}_{[g[i] - g[j_2] \geq 0]}\right) \end{aligned}$$

由于 $\mathbb{1}_{[P]} \in \{0, 1\}$ ，所以：

$$\mathbb{1}_{[g[i] - g[j_1] \geq 0]} - \mathbb{1}_{[g[i] - g[j_2] \geq 0]} \in \{-1, 0, 1\} $$

又因为 $f[j_1] - f[j_2] \geq 1$ ，所以：

C(i, j_1) - C(i, j_2) \geq 1 + (-1) = 0

因此 $C(i, j_2) \leq C(i, j_1)$ ，即 $j_2 \preceq_{i} j_1$ 。

情况2： $f[j_1] = f[j_2]$ 且 $g[j_1] \leq g[j_2]$

此时代价函数的差值为：

$$C(i, j_1) - C(i, j_2) = \mathbb{1}_{[g[i] - g[j_1] \geq 0]} - \mathbb{1}_{[g[i] - g[j_2] \geq 0]} $$

我们需要证明：$\mathbb{1}_{[g[i] - g[j_1] \geq 0]} - \mathbb{1}_{[g[i] - g[j_2] \geq 0]} \geq 0$

由于 $g[j_1] \leq g[j_2]$ ，我们有：

如果 $g[i] - g[j_2] \geq 0$ ，则 $g[i] - g[j_1] \geq g[i] - g[j_2] \geq 0$

此时 $\mathbb{1}_{[g[i] - g[j_1] \geq 0]} = 1$ ， $\mathbb{1}_{[g[i] - g[j_2] \geq 0]} = 1$

差值 = $1 - 1 = 0$
如果 $g[i] - g[j_2] < 0$ ，则可能有两种情况：

(a) $g[i] - g[j_1] \geq 0$ ：此时差值 = $1 - 0 = 1 > 0$

(b) $g[i] - g[j_1] < 0$ ：此时差值 = $0 - 0 = 0$

因此在所有情况下，都有 $C(i, j_1) - C(i, j_2) \geq 0$ ，即 $j_2 \preceq_{i} j_1$ 。

推论3.1：在单调队列中，如果 $j_1 < j_2$ 且满足引理3.1的条件，则 $j_1$ 可以被安全删除，因为它永远不会成为最优决策。

3.3.3 动态规划正确性证明

定理3.1（DP最优子结构）：状态转移方程

f[i] = \min_{i-K \leq j < i} C(i, j)

具有最优子结构性质，即 $f[i]$ 确实给出了前 $i$ 个位置的最优解。

证明：

使用数学归纳法。

基础情况： $i = 0$ ， $f[0] = 0$ 显然正确（空序列无需划分）。

归纳假设：假设对于所有 $k < i$ ， $f[k]$ 都是前 $k$ 个位置的最优解。

归纳步骤：我们需要证明 $f[i]$ 是前 $i$ 个位置的最优解。

设前 $i$ 个位置的任意一个合法划分方案 $\mathcal{P}$ ，设最后一个区间为 $[j+1, i]$ （其中 $i-K \leq j < i$ ），前面 $j$ 个位置的划分为 $\mathcal{P}'$ 。

设 $\mathcal{P}$ 中"更赛牛较多或均势"的区间数为 $\text{cost}(\mathcal{P})$ ，则：

$$\text{cost}(\mathcal{P}) = \text{cost}(\mathcal{P}') + \mathbb{1}_{[[j+1,i]\text{ 是更赛牛较多或均势}]} $$

由归纳假设， $\mathcal{P}'$ 的最优解为 $f[j]$ ，因此：

$$\text{cost}(\mathcal{P}) \geq f[j] + \mathbb{1}_{[g[i] - g[j] \geq 0]} = C(i, j) $$

由于 $f[i] = \min_{i-K \leq j < i} C(i, j)$ ，所以对于任意合法划分 $\mathcal{P}$ ：

$$\text{cost}(\mathcal{P}) \geq \min_{i-K \leq j < i} C(i, j) = f[i] $$

因此 $f[i]$ 确实是最优解。

定理3.2（单调队列算法正确性）：使用单调队列维护的算法能够正确计算出所有的 $f[i]$ 值。

证明：

我们需要证明两点：

队列中始终包含最优决策点
队头始终是当前的最优决策点

命题1（包含性）：对于任意位置 $i$ ，在计算 $f[i]$ 时，所有可能成为最优决策的 $j \in [i-K, i-1]$ 都在队列中，或者存在队列中的某个 $j'$ 使得 $j' \preceq_{i} j$ 。

证明：反证法。假设存在某个 $j$ 是最优决策但不在队列中，且队列中没有比它更优的决策。

由于 $j$ 曾经被加入队列（所有位置都会加入），所以 $j$ 必然是被删除了。删除只有两种情况：

(a) 从队头删除（超出范围）：但 $j \in [i-K, i-1]$ ，矛盾。

(b) 从队尾删除（被更优的决策支配）：存在某个 $j' > j$ 满足引理3.1的条件。由引理3.1， $j' \preceq_{i} j$ ，即 $j'$ 不劣于 $j$ ，矛盾（因为假设 $j$ 是最优且队列中没有比它更优的）。

因此假设不成立，命题1得证。

命题2（队头最优性）：在计算 $f[i]$ 时，队头元素 $q[\text{head}]$ 必然是所有合法决策中的最优者之一。

证明：由队列的维护规则，队列中的元素按照"优先级"递减排列（依据引理3.1的比较标准）。队头元素是队列中"优先级"最高的，结合命题1，队头元素必然是最优决策。

由命题1和命题2，定理3.2得证。

3.3.4 时间复杂度严格证明

定理3.3（时间复杂度）：单调队列优化的DP算法的时间复杂度为 $\Theta(N)$ 。

证明：

我们分析每个元素的操作次数。

入队操作：每个元素 $i \in \{0, 1, \ldots, n\}$ 最多入队一次。总入队次数 $\leq n+1 = O(N)$ 。

出队操作：分为两种：

从队头出队（超出范围）：每个元素最多出队一次，总次数 $\leq n+1 = O(N)$
从队尾出队（被支配）：每个元素最多出队一次，总次数 $\leq n+1 = O(N)$

每个元素的生命周期：最多被入队一次，最多被出队一次。

状态转移：对于每个 $i \in \{1, 2, \ldots, n\}$ ，执行一次 $O(1)$ 的转移。总次数 $= n = O(N)$ 。

因此，总时间复杂度为：

T(N) = O(N) + O(N) + O(N) = O(N)

又因为必须至少读取所有 $N$ 个字符，所以 $T(N) = \Omega(N)$ 。

综上， $T(N) = \Theta(N)$ 。

3.3.5 空间复杂度证明

定理3.4（空间复杂度）：算法的空间复杂度为 $\Theta(N)$ 。

证明：

算法使用的空间包括：

输入数组 s： $O(N)$
前缀和数组 g： $O(N)$
DP数组 f： $O(N)$
单调队列 q：最多存储 $K$ 个元素， $O(K) = O(N)$

总空间： $S(N) = O(N) + O(N) + O(N) + O(N) = O(N)$

又因为必须至少存储输入，所以 $S(N) = \Omega(N)$ 。

综上， $S(N) = \Theta(N)$ 。

四、代码实现

4.1 核心代码分析

#include <bits/stdc++.h>
using namespace std;
const int N = 3e5 + 5;
int n, k, f[N], g[N];
int q[N], head, tail;
char s[N];

int main() {
    scanf("%d%d%s", &n, &k, s + 1);

    // 计算前缀和：G为+1，H为-1
    for (int i = 1; i <= n; i++) {
        if (s[i] == 'G')
            g[i] = g[i - 1] + 1;
        else
            g[i] = g[i - 1] - 1;
    }

    q[tail++] = 0; // 初始时0入队

    for (int i = 1; i <= n; i++) {
        // 超范围出队
        while (head < tail && i - k > q[head])
            head++;

        // 取出队头进行状态转移
        f[i] = f[q[head]] + (g[i] - g[q[head]] >= 0);

        // f[i]入队
        while (head < tail) {
            if (f[i] < f[q[tail - 1]] || 
                (f[i] == f[q[tail - 1]] && g[i] > g[q[tail - 1]]))
                tail--;
            else
                break;
        }

        q[tail++] = i;
    }

    cout << f[n];
    return 0;
}

4.2 代码详解

步骤1：前缀和预处理

for (int i = 1; i <= n; i++) {
    if (s[i] == 'G')
        g[i] = g[i - 1] + 1;
    else
        g[i] = g[i - 1] - 1;
}

将字符转换为数值：G → +1，H → -1
计算前缀和，便于快速判断区间的"更赛牛优势"

步骤2：单调队列初始化

q[tail++] = 0; // 初始时0入队

位置0表示"空序列"，是一个有效的决策点

步骤3：DP转移（主循环）

for (int i = 1; i <= n; i++) {
    // 出队：超出范围的决策点
    while (head < tail && i - k > q[head])
        head++;

    // 转移：使用队头元素
    f[i] = f[q[head]] + (g[i] - g[q[head]] >= 0);

    // 入队：维护单调性
    while (head < tail) {
        if (f[i] < f[q[tail - 1]] || 
            (f[i] == f[q[tail - 1]] && g[i] > g[q[tail - 1]]))
            tail--;
        else
            break;
    }

    q[tail++] = i;
}

单调性维护规则：

如果新元素 $i$ 比队尾元素更优（ $f$ 值更小，或 $f$ 值相同但 $g$ 值更大），则删除队尾
这样保证队列中的元素按照"优先级"单调递减

五、样例分析

5.1 样例输入

7 2
HGHGGHG

5.2 计算过程

前缀和计算：

i:    0  1  2  3  4  5  6  7
s:    -  H  G  H  G  G  H  G
g:    0 -1  0 -1  0  1  0  1

DP过程：

$i$	队列状态	队头 $j$	$g[i] - g[j]$	$f[i]$
1	[0]	0	-1 - 0 = -1	0 + 0 = 0
2	[0, 1]	0	0 - 0 = 0	0 + 1 = 1
3	[1, 2]	1	-1 - (-1) = 0	0 + 1 = 1
4	[2, 3]	2	0 - 0 = 0	1 + 1 = 2
5	[3, 4]	3	1 - (-1) = 2	1 + 1 = 2
6	[4, 5]	4	0 - 0 = 0	2 + 1 = 3
7	[5, 6]	5	1 - 1 = 0	2 + 1 = 3

最优划分方案：

区间 [1, 2]：HG，均势，贡献1
区间 [3, 4]：HG，均势，贡献1
区间 [5, 7]：GHG，更赛牛较多，贡献1

总计：3个"更赛牛较多或均势"的区。

5.3 样例输出

六、复杂度总结

基于第三部分的严格数学证明（定理3.3和定理3.4），我们得到：

6.1 时间复杂度

结论： $\Theta(N)$

详细分析：

前缀和预处理： $O(N)$
单调队列DP：每个元素最多入队一次、出队一次，总操作数 $O(N)$
状态转移：每个状态 $O(1)$ 计算，共 $N$ 个状态
总时间复杂度： $\Theta(N)$ （紧确界）

6.2 空间复杂度

结论： $\Theta(N)$

详细分析：

输入数组 s： $O(N)$
前缀和数组 g： $O(N)$
DP数组 f： $O(N)$
单调队列 q： $O(\min(K, N)) = O(N)$
总空间复杂度： $\Theta(N)$ （紧确界）

6.3 复杂度优化效果

算法	时间复杂度	空间复杂度	可通过数据规模
朴素DP	$O(NK)$	$O(N)$	$N \leq 10^4$
单调队列优化DP	$\Theta(N)$		$N \leq 3 \times 10^5$ ✓

优化倍数：从 $O(NK)$ 到 $O(N)$ ，当 $K = N$ 时，优化了 $N$ 倍！

七、关键技巧总结

7.1 前缀和转化

将"更赛牛较多或均势"的判断转化为：

\text{count}(G) - \text{count}(H) \geq 0

通过前缀和快速计算区间的"优势值"。

7.2 单调队列优化DP

适用场景：

转移只依赖于一个滑动窗口内的状态
存在明确的"优劣比较"规则

优化效果：

从 $O(NK)$ 降低到 $O(N)$

7.3 决策单调性

当前问题的决策单调性体现在：

如果 $f[j_1] > f[j_2]$ ，则 $j_1$ 永远不如 $j_2$ 优
如果 $f[j_1] = f[j_2]$ 且 $g[j_1] < g[j_2]$ ，则 $j_1$ 也不如 $j_2$ 优

八、扩展思考

8.1 相关问题

最长不下降子序列：也可以用单调队列优化
滑动窗口最值：单调队列的经典应用
斜率优化DP：更复杂的决策单调性

8.2 变式问题

如果要求每个区间恰好包含 $K$ 个牧草地？
如果要求最小化"荷斯坦牛较多"的区的数量？（对称问题）
如果有多种奶牛种族？（多维前缀和）

九、算法正确性完整证明总结

9.1 证明链条

我们的证明构成了一个完整的链条：

定理1.1（前缀和等价性）

\text{区间更赛牛较多或均势} \iff g[i] - g[j] \geq 0

$\Downarrow$

定理2.1-2.3（DP正确性）

状态定义正确
转移方程正确
问题可解 $\Downarrow$

引理3.1（决策支配性）

$$f[j_1] > f[j_2] \text{ 或 } (f[j_1] = f[j_2] \land g[j_1] \leq g[j_2]) \implies j_2 \preceq_{i} j_1 $$