自动搬运

查看原文

来自洛谷，原作者为

	Anonymely 330。

搬运于2025-08-24 23:02:13，当前版本为作者最后更新于2024-08-17 15:58:01，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

上午上课放了一堆 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;
}