糖果色的梦

· · 题解

上午上课放了一堆 Ynoi，不想听了来看了眼比赛，然后被本题硬控半小时。

首先注意到常规 dp 思路似乎无从下手，很类似线头 dp 却与值域相关，同时也没有像 NOI2022 移除石子 一样优良的性质做到 dfa 最小化，考虑网络流。

首先 23 操作给不少于 k 个人修改是诈骗，因为发现修改 k 个剩下的用 1 操作贡献没变，发现这个区间加1的操作很像 NOI2008 志愿者招募，考虑对每个点设出变量。定义 a_i 表示对第 i 个人进行的 1 操作次数，b_i 表示以第 i 个人为右端点的 2 操作次数，c_i 表示以第 i 个人为右端点的 3 操作次数。

能得到 a_i + \sum_{j=i}^{i+k-1} b_j - c_j \ge v_i，其中 v 是题目中给定的 a 数组。

我们在 n 个式子上补上 x_i 表示平衡，再加入两个式子 x_0 = 0, x_{n+1} = 0，相邻两项相减得到

a_i - a_{i+1}+(b_i-c_i)-(b_{i+k}-c_{i+k}) + x_i - x_{i+1} = v_i - v_{i+1}

移项后发现每个变量只出现两次，且在所有式子中一定为一正一负，把式子看成点，从负点向正点连 (inf,cost) 的边，而对于 v，若该式子常数项 d=v_{i+1}-v_i 为正则连 (S,i,d,0)，否则连 (i,T,-d,0)。

费用流被卡T了，spfa 魔怔优化之后才过。

#include<bits/stdc++.h>
using namespace std;

#define QwQ330AwA return 0
#define ll long long

const int N = 1005;
const int M = 100005;
const ll inf = 1e18;
int S, T;
struct Edge {   
    int to, nxt;
    ll w;
    int c;
} e[M];
int head[N], cnt;
void clear() {
    memset(head, 0, sizeof(head));
    cnt = 0;
}
void add(int u, int v, ll w, int c) {
    e[++cnt] = {v, head[u], w, c};
    head[u] = cnt;
}
void add_edge(int u, int v, ll w, int c) {
    add(u, v, w, c);
    add(v, u, 0, -c);
}
ll dep[N];
bitset <N> vis;
int now[N];
bool bfs() {
    memset(dep, 0x3f, sizeof(dep));
    vis.reset();
    ll lim = dep[0];
    deque <int> q;
    dep[S] = 0;
    now[S] = head[S];
    vis[S] = 1;
    q.push_back(S);
    while (!q.empty()) {
        int u = q.front();
        q.pop_front();
        vis[u] = 0;
        for (int i = head[u]; i; i = e[i].nxt) {
            int v = e[i].to;
            if (dep[v] > dep[u] + e[i].c && e[i].w) {
                dep[v] = dep[u] + e[i].c;
                now[v] = head[v];
                if (!vis[v]) {
                    if (!q.empty() && dep[v] < dep[q.front()]) q.push_front(v);
                    else q.push_back(v);
                    vis[v] = 1;
                }
            }
        }
    }
    return dep[T] != lim;
}
ll dfs(int u, ll flow) {
    if (u == T) return flow;
    ll sum = 0, tmp;
    vis[u] = 1;
    for (int i = now[u]; i; i = e[i].nxt) {
        int v = e[i].to;
        now[u] = i;
        if (!vis[v] && dep[v] == dep[u] + e[i].c && e[i].w) {
            tmp = dfs(v, min(flow - sum, e[i].w));
            sum += tmp;
            e[i].w -= tmp;
            #define rev(x) ((x - 1) ^ 1) + 1
            e[rev(i)].w += tmp;
            if (sum == flow) break;
        }
    }
    if (sum == flow) vis[u] = 0;
    return sum;
}
ll dinic() {
    ll ans = 0;
    while (bfs()) ans += dfs(S, inf) * dep[T];
    return ans;
}

int n, k, B, C, v[N];
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> k >> B >> C;
    for (int i = 1; i <= n; i++) cin >> v[i];
    S = n + 1, T = n + 2;
    for (int i = 0; i < n; i++) {
        add_edge(i, i + 1, inf, 1);
        add_edge(i + 1, i, inf, 0);
        if (i + k <= n) add_edge(i, i + k, inf, k - B);
        if (i + k <= n) add_edge(i + k, i, inf, -C);
    }
    for (int i = 0; i <= n; i++) {
        int d = v[i + 1] - v[i];
        if (d > 0) add_edge(S, i, d, 0);
        else if (d < 0) add_edge(i, T, -d, 0);
    }
    cout << dinic() << '\n';
    QwQ330AwA;
}