题解：AT_abc404_e 茶碗和豆子

ZZ0520 · 2025-05-09 10:30:03 · 题解

题目大意

有 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

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