今天我们来看CSP202503B. 机器人饲养指南这道题目

首先我们来复习 一下完全背包DP：

有一个容量为 V 的背包，给定 N 种物品： 每种物品有无穷多个，第 i 件物品体积 wᵢ，价值 vᵢ。 每种物品可以选 0、1、2、…… 任意件，求背包不超容量时能装的最大总价值。

令dp[i][j]表示前i种物品，容量为j的最大值

假设不选第i种物品，结果为dp[i-1][j]

选第i种物品，结果为dp[i][j-wᵢ]+vᵢ （注意：和每个物品只能选1件的01背包相比，此处可以继续选第i种物品，所以第一维仍然为i）

即                                               dp[i][j]=max(dp[i-1][j],dp[i][j-wᵢ]+vᵢ)

一维空间优化

容量从小到大枚举，更新dp[j]时dp[j-w]已经被修改

即                                               dp[j]=max(dp[j],dp[j-w[i]]+v[i])

回到本题，我们令dp[i]表示苹果总数为i时能获得的最大心情值，每天投喂的苹果数量即为物品重量，获得的心情值为价值，即可得到如下转移

                                                   dp[i]=max(dp[i],dp[i-j]+a[j])

结合刚才完全背包的写法，从小到大枚举j从1到m，就得到了如下代码

#include <bits/stdc++.h>
using namespace std;

#define itn int
#define ll long long
#define ld long double
#define mod 998244353

const int INF = 1e9;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int n, m;
    cin >> n >> m;
    vector<int> a(m + 1);
    for (int i = 1; i <= m; i++) {
        cin >> a[i];
    }
    vector<int> dp(n + 1, -INF);
    dp[0] = 0;
    for (int j = 1; j <= m; j++) {
        int val = a[j];
        for (int i = j; i <= n; i++) {
            dp[i] = max(dp[i], dp[i - j] + val);
        }
    }
    cout << dp[n] << endl;
    return 0;
}

感谢阅读，欢迎在评论区讨论！

转载标明出处