题解 P5202 【[USACO19JAN]Redistricting】

· · 题解

这里用单调队列实现，吊打堆，时间复杂度只需O(n)

首先看到此题想到DP。容易得出下面的式子：

记sum[i]为1 ~ i 中H的个数减去G的个数

f[i] = min \left\{f[j] + (sum[i] - sum[j] <= 0)\right\} (i - j <= k)

由于枚举j肯定要超时，我们想到用数据结构来维护DP

如果没有(sum[i] - sum[j] <= 0)这个东西，我们很容易想到用单调队列来维护，但加上后面这个呢？由于它不是1就是0，而且sum[i]值固定，那我们可以分类讨论：

对于 \forall p, q (p, q满足转移条件)：

若f[p] \neq f[q]，则我们肯定把小的放队首，因为即使它要加1也一定不会劣于另一个

若f[p] = f[q], 则我们把sum小的放队首，这样拿sum[i]减后才更可能不小于0

有了以上推论&细节&卡常，你就不仅能AC，RP好还能进入最优解第一面（女装有益减小常数QwQ）

以下是代码（131ms）

#pragma GCC optimize ("Ofast")
#include <cstdio>
using namespace std;

inline void read (int& s) {
    s = 0;
    static char c = getchar ();
    while (c < '0' || c > '9') c = getchar ();
    while (c >= '0' && c <= '9') s = (s << 3) + (s << 1) + (c & 15), c = getchar ();
    return ;
}

const int N = 300007;
int n, k, f[N], sum[N];
int Q[N], H, T;

int main () {
    read (n), read (k);
    register int i; for (i = 1; i <= n; ++i) sum[i] = sum[i - 1] + (getchar () == 'H' ? 1 : -1);
    Q[T++] = 0; //刚开始前0头牛答案为0
    for (i = 1; i <= n; ++i) {
        while (H < T && i - Q[H] > k) ++H; //单调队列的出队操作
        f[i] = f[Q[H]] + (sum[i] - sum[Q[H]] <= 0);
        while (H < T) {
            if (f[i] < f[Q[T - 1]] || (f[i] == f[Q[T - 1]] && sum[i] < sum[Q[T - 1]])) --T;
            else break;
        } //入队操作，注意一下细节
        Q[T++] = i;
    }
    printf ("%d\n", f[n]);
    return 0;
}

个人觉得单调队列好写，好记，好快，为什么还用堆来维护呢