题目大意

有

n

个碗编号为

1\sim n-1

，第

0

个碗中无豆子，第

i

个碗中有

a_i

个豆子，它的所有豆子可以移动到前

c_i

个碗中的任意一个，求将所有碗中的豆子移动到

0

号碗里最少需要几次移动。

解法

我们可以设计一个记忆化搜索：

对于每一个碗，我们记录有那些碗可以把豆子转移到那个碗里。

然后我们可以把它想象成最开始所有豆子都在

0

号碗里，我们要把所有豆子移到有豆子的那些碗里。

我们从

0

号碗开始，向后移动豆子。但我们注意到有豆子的碗是必须得移到的，不然它就会没有豆子，所以在搜索时，记录接下来要到哪一个碗里，每次只要可以从转到那里，那就直接转过去。

但需要注意的是，我们的记忆化搜索 dfs(x) 表示把 x 后面的碗的所有豆子都移到 x 这个碗最少需要几步，所以由于最后一个有豆子的碗及以后的所有碗后面都没有豆子，所以都为

0

。（赛时就因为这个没拿分）

代码

CPP

#include <bits/stdc++.h>
#define int long long
const int N = 1e5 + 5;
const int Mod = 1e9 + 7;
using namespace std;
int n;
int sum, ans;
int c[N], a[N];
int f[N];
vector<int> froms[N];
vector<int> toes;
int dfs(int x, int y, int to)
{
    if (f[x])
    {
        return f[x];
    }
    if (x >= toes.back())
    {
        return 0;
    }
    if (x == toes[to])
    {
        to++;
    }
    int mi = 1e18;
    for (int i : froms[x])
    {
        if (i > toes[to])
        {
            continue;
        }
        mi = min(mi, dfs(i, y + 1, to));
    }
    f[x] = mi + 1;
    return mi + 1;
}
signed main()
{
    cin >> n;
    n--;
    for (int i = 1; i <= n; i++)
    {
        cin >> c[i];
        for (int j = i - c[i]; j <= i - 1; j++)
        {
            froms[j].push_back(i);
        }
    }
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        if (a[i])
        {
            toes.push_back(i);
        }
    }
    ans = dfs(0, 0, 0);
    cout << ans;
    return 0;
}

提交记录

题解：AT_abc404_e [ABC404E] Bowls and Beans

文章操作

题目大意

解法

代码

相关推荐

评论

题解：AT_abc404_e [ABC404E] Bowls and Beans