自动搬运

查看原文

来自洛谷，原作者为

	szh_AK_all S挂分挂到被洛谷7级勾卡线|I can do all things

搬运于2025-08-24 23:09:12，当前版本为作者最后更新于2025-02-02 19:25:23，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

好题啊好题（赞赏）。

分析

考虑 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$ 时，根据题意分为如下两种情况：

• $b_i=b_j$，即表演者 $i,j$ 喷的酒的方向相同。若在无阻挡的情况下。表演者 $i$ 喷的酒可以到达比表演者 $j$ 喷的酒可以到达的更远的位置，那么显然我们留下表演者 $i$ 而不留下表演者 $j$ 是更优的；如果表演者 $i$ 喷的酒只能到达比表演者 $j$ 喷的酒可以到达的更近的位置，那么若留下表演者 $i,j$，表演者 $i,j$ 所能到达的位置形成的区间与单独考虑表演者 $i,j$ 所能到达的位置形成的区间是相同的。

• $b_i\ne b_j$，即表演者 $i,j$ 喷的酒的方向不同，此时表演者 $j$ 会寄。若 $b_i=1,b_j=-1$，此时 $j$ 一定大于 $i$，在转移 $f_{j-a_j\sim j}$ 时由于 $j$ 喷的酒可以到达 $i$，那么留下 $i$ 且 $b_i=1$ 一定不优；若 $b_i=-1,b_j=1$ 则同理。因此转移时不存在有表演者愤怒离场的情况。

下面是 $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);
}

记得点赞谢谢喵。