题解：P11656 「FAOI-R5」喷酒大赛

· · 题解

好题啊好题（赞赏）。

分析

考虑 dp。设 f_i 表示覆盖了 1\sim i 这些位置所需要的最少表演者数量，那么我们枚举每位表演者，考虑其会对哪些位置产生影响。对于表演者 i，若其方向属性 b_i 为 -1，则表演者 i 可以将满足 i\ge k\ge i-a_i 的前缀 1\sim k 与区间 k\sim i 连接起来，那么在进行转移时更新 f_{i-a_i \sim i} 即可，具体的，设 ans=\min_{j=\max(0,i-a_i)}^i f_j，则转移式为 f_k=\min(f_k,ans+1)。你可能有疑问：满足 f_j 值取到的最小的 j 如果在转移时比 k 大怎么办？注意点这种转移是不会影响 f_k 的值的。

若表演者 i 的方向属性为 1 时同理。

但是这样的 dp 为什么是对的？

考虑当表演者 i 喷的酒碰到了表演者 j 时，根据题意分为如下两种情况：

下面是 O(n^2) 的暴力代码。

#include <bits/stdc++.h>
using namespace std;
int a[500005], k[500005], f[1005];

int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    for (int i = 1; i <= n; i++)
        cin >> k[i];
    memset(f, 0x3f, sizeof(f));
    f[0] = 0;
    for (int i = 1; i <= n; i++) {
        int ans = 1000000000, tmp = 1000000000;
        for (int j = i - 1; j <= min(n, i + a[i]); j++)
            tmp = min(tmp, f[j] + 1);
        for (int j = max(0, i - a[i]); j <= i; j++)
            ans = min(ans, f[j] + 1);
        for (int j = max(0, i - a[i]); j <= i; j++)
            f[j] = min(f[j], ans);
        for (int j = i - 1; j <= min(n, i + a[i] - 1); j++)
            f[j] = min(f[j], tmp);
    }
    cout << f[n];
}

注意到计算区间最小 dp 值以及区间更新可以用线段树来维护，于是复杂度便正确了。

#include <bits/stdc++.h>
using namespace std;
int a[500005], k[500005], f[500005];

struct node {
    int ans, la;
    node(int aa = 1000000000, int bb = 1000000000) {
        ans = aa;
        la = bb;
    }
} t[500005 << 2];

void pushdown(int d) {
    if (t[d].la == 1000000000)
        return;
    t[d * 2].ans = min(t[d * 2].ans, t[d].la), t[d * 2].la = min(t[d * 2].la, t[d].la);
    t[d * 2 + 1].ans = min(t[d * 2 + 1].ans, t[d].la), t[d * 2 + 1].la = min(t[d * 2 + 1].la, t[d].la);
    t[d].la = 1000000000;
}

void bu(int d, int l, int r) {
    if (l == r) {
        t[d].ans = t[d].la = 1000000000;
        return;
    }
    int mid = (l + r) / 2;
    bu(d * 2, l, mid);
    bu(d * 2 + 1, mid + 1, r);
    t[d].ans = min(t[d * 2].ans, t[d * 2 + 1].ans);
}

void add(int d, int l, int r, int ll, int rr, int z) {
    if (ll <= l && r <= rr) {
        t[d].ans = min(t[d].ans, z);
        t[d].la = min(t[d].la, z);
        return;
    }
    pushdown(d);
    int mid = (l + r) / 2;
    if (ll <= mid)
        add(d * 2, l, mid, ll, rr, z);
    if (rr > mid)
        add(d * 2 + 1, mid + 1, r, ll, rr, z);
    t[d].ans = min(t[d * 2].ans, t[d * 2 + 1].ans);
}

int ask(int d, int l, int r, int ll, int rr) {
    if (ll <= l && r <= rr)
        return t[d].ans;
    pushdown(d);
    int mid = (l + r) / 2, ans = 1000000000;
    if (ll <= mid)
        ans = min(ans, ask(d * 2, l, mid, ll, rr));
    if (rr > mid)
        ans = min(ans, ask(d * 2 + 1, mid + 1, r, ll, rr));
    return ans;
}

int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    for (int i = 1; i <= n; i++)
        cin >> k[i];
    bu(1, 1, n);
    for (int i = 1; i <= n; i++) {
        int ans = 1000000000, tmp = 1000000000;
        tmp = ask(1, 1, n, max(1, i - 1), min(n, i + a[i] - 1));
        ans = ask(1, 1, n, max(1, i - a[i]), i);
        if (i - 1 == 0)
            tmp = 0;
        if (i - a[i] <= 0)
            ans = 0;
        ans++, tmp++;
        add(1, 1, n, max(1, i - a[i]), i, ans);
        add(1, 1, n, max(1, i - 1), min(n, i + a[i] - 1), tmp);
    }
    cout << ask(1, 1, n, n, n);
}

记得点赞谢谢喵。