专栏文章

题解：AT_abc404_e [ABC404E] Bowls and Beans

tthis54
AT_abc404_e题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mipdjlm3
此快照首次捕获于
2025/12/03 10:14
3 个月前
此快照最后确认于
2025/12/03 10:14
3 个月前
查看原文

一道需要思考转换的 dpdp 题目

首先我们简单想一下。
对于两碗豆子，第一个能直接到0号碗，第二个只能到第一个碗，那只可能是先把第二个碗的豆子合并到第一个碗，再把第一个碗的豆子一起带到0号碗最优。
想明白这点就懂了，最后所有的豆子都是要被带到0号碗的，所有像刚刚我们所说的这种情况，第二个碗对于第一个碗的最终贡献是没有影响的，所以我们任意将后面的碗合并到前面有豆子的碗就好了，等我们操作这个被合并的碗时继续向前（可能没有这么严谨，但我觉得这样更好理解）。
得出结论：每一个碗如果有豆子，那么它对操作数量的贡献值是向左一直走走到下一个有豆子碗的最少步数。
这个明显是个 dpdp 啊。
定义 dp[i]dp[i] 为第 ii 个碗能走到有豆子的碗的最小步数。
分类讨论：
如果第 ii 个碗有豆子，则 dp[i]=0dp[i]=0 ，因为它自己本身就是有豆子的碗。
如果第ii个碗没豆子，则 dp[i]dp[i] 为 i−c[i]i-c[i] 到 i−1i-1 中 dpdp 数组最小值 +1+1 。
答案统计时，如果第 ii 个碗有豆子，则答案也为则 dp[i]dp[i] 为 i−c[i]i-c[i] 到 i−1i-1 中 dpdp 数组最小值 +1+1 （大家应该还能看懂吧）。
题解中有 O(n2)O(n^2) 的解法了，但是我们容易注意到所有对数组的操作只有两类，单点修改，区间最小值查询，容易想到用线段树维护。
CPP
#include <bits/stdc++.h>
#define ls(x) x<<1
#define rs(x) x<<1|1
using namespace std;
int n, c[2010], a[2010];
int dp[8010];//这个dp数组是一个线段树
int ans;
void modify(int l, int r, int nw, const int& x, const int& k)
{
	if (l == r)
	{
		dp[nw] = k;
		return;
	}//在dp过程中，我们保证每个节点有且仅有一次修改
	int mid = (l + r) >> 1;
	if (x <= mid) modify(l, mid, ls(nw), x, k);
	else modify(mid + 1, r, rs(nw), x, k);
	dp[nw] = min(dp[ls(nw)], dp[rs(nw)]);//维护最小值
}
int query(const int& pl, const int& pr, int l, int r, int nw)
{
	if (pl <= l && r <= pr) return dp[nw];
	int ans = 1e9, mid = (l + r) >> 1;
	if (pl <= mid) ans = min(ans, query(pl, pr, l, mid, ls(nw)));
	if (mid < pr) ans = min(ans, query(pl, pr, mid + 1, r, rs(nw)));
	return ans;
}
int main()
{
	cin >> n;
	for (int i = 1;i < n;i++) cin >> c[i];
	for (int i = 1;i < n;i++) cin >> a[i];
	//dp[0]=0;
	for (int i = 1;i < n;i++)
	{
		int val = query(i - c[i], i - 1, 0, n, 1) + 1;
		if (a[i] > 0) ans += val;//i上有豆子，更新答案
		else modify(0, n, 1, i, val);
	}
	cout << ans;
	return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...