题解：AT_abc404_e [ABC404E] Bowls and Beans

· · 题解

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

首先我们简单想一下。

对于两碗豆子，第一个能直接到0号碗，第二个只能到第一个碗，那只可能是先把第二个碗的豆子合并到第一个碗，再把第一个碗的豆子一起带到0号碗最优。

想明白这点就懂了，最后所有的豆子都是要被带到0号碗的，所有像刚刚我们所说的这种情况，第二个碗对于第一个碗的最终贡献是没有影响的，所以我们任意将后面的碗合并到前面有豆子的碗就好了，等我们操作这个被合并的碗时继续向前（可能没有这么严谨，但我觉得这样更好理解）。

得出结论：每一个碗如果有豆子，那么它对操作数量的贡献值是向左一直走走到下一个有豆子碗的最少步数。

这个明显是个 dp 啊。

定义 dp[i] 为第 i 个碗能走到有豆子的碗的最小步数。

分类讨论：

如果第 i 个碗有豆子，则 dp[i]=0 ，因为它自己本身就是有豆子的碗。

如果第i个碗没豆子，则 dp[i] 为 i-c[i] 到 i-1 中 dp 数组最小值 +1 。

答案统计时，如果第 i 个碗有豆子，则答案也为则 dp[i] 为 i-c[i] 到 i-1 中 dp 数组最小值 +1 （大家应该还能看懂吧）。

题解中有 O(n^2) 的解法了，但是我们容易注意到所有对数组的操作只有两类，单点修改，区间最小值查询，容易想到用线段树维护。

#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;
}