题解：AT_abc404_e 茶碗和豆子

题目大意

有

N

个茶碗，它们排成一排，从左往右依次编号

0,1,\cdots,N-1

，初始时，茶碗

0

为空，茶碗

i

有

a_i

颗豆子，并标有数字

c_i

。

每次操作你可以：任选一个茶碗

i

，取出一些豆子，将这些豆子分配到茶碗

i-c_i,i-c_i+1,\cdots,i-1

号中。

求将所有豆子都移到茶碗

0

的最少操作次数。

思路

因为贪心不好贪，所以我们直接考虑动态规划。
对于每一个 $i$ 来说，能放的区间其实是固定的，而且我们肯定不会把一个茶碗的豆子分开放到好几个茶碗，因为这样没有意义。
所以如果我们能求出 [i-c[i],i-1] 到 $0$ 号茶碗最小的操作次数， $i$ 号茶碗就应该转移到最小处。
所以 $dp_i$ 就表示从 $i$ 号位置放到 $0$ 号位置需要操作几次。
状态： $dp_i=\min(dp_i,dp_j+1)$ ， $j$ 为 $i-c_i,i-c_i+1,\cdots,i-1$ 。

Code

CPP

#include <bits/stdc++.h>
using namespace std;
const int N = 2005;
int c[N], a[N], f[N];
int main(){
    int n;
    cin >> n;
    for (int i = 1; i < n; i++)
        cin >> c[i];
    for (int i = 1; i < n; i++)
        cin >> a[i];
    int ans = 0;
    for (int i = 1; i < n; i++){
        f[i] = 1e9;
        for (int j = i - c[i]; j < i; j++){
            f[i] = min(f[i], f[j] + 1);
        }
        if (a[i]){
            ans += f[i];
            f[i] = 0;//如果后面的茶碗放到这个茶碗，就不需要再走一遍前面的过程
        }
    }
    cout << ans << endl;
    return 0;
}

题解：AT_abc404_e 茶碗和豆子

文章操作

题目大意

思路

Code

相关推荐

评论

题解：AT_abc404_e 茶碗和豆子