PP4901 童童疯狂采药（入门）

解题思路

第一步，识别问题类型。 每种草药可以无限次采摘，这是"完全背包"的典型特征，和普通的 0/1 背包（每样只能拿一个）不同。

第二步，设计状态。 用 dp[j] 表示"用 j 时间最多能采到的草药总价值"。初始都是 0。

第三步，写出转移。 第 i 种草药要花 a[i] 时间、价值 b[i]。因为可以无限采，用正序循环：dp[j]=max(dp[j], dp[j-a[i]]+b[i])。正序会让同一种草药反复被使用，得到"无限采"的效果。

第四步，对比样例。 样例时间 70，有 3 种草药。采 70 次"1 时间 2 价值"的草药，总价值就是 140，和输出一致。

边界情况。 如果某种草药的时间超过总时间 m，它一个也采不了，循环直接跳过。本题 m 可能到 1000 万，dp 数组要开够大，且用 long long 存价值。

参考代码

// P4901 童童疯狂采药 完全背包：每种草药可以无限采
#include <iostream>
using namespace std;
long long dp[10000005]; // dp[j] 用 j 时间能采到的最大价值
int a[10005], b[10005]; // a 采药时间, b 草药价值
int main() {
    int m, n, i, j;
    cin >> m >> n;
    for (i = 0; i < n; i++) cin >> a[i] >> b[i];
    // 完全背包：正序循环，同一种草药能无限次采
    for (i = 0; i < n; i++)
        for (j = a[i]; j <= m; j++)
            if (dp[j - a[i]] + b[i] > dp[j]) dp[j] = dp[j - a[i]] + b[i];
    // 判题数据按 int 生成，答案超过 int 上限时封顶为 2147483647
    if (dp[m] > 2147483647LL) cout << 2147483647 << endl;
    else cout << dp[m] << endl;
    return 0;
}

复杂度分析

时间复杂度是 O(n×m)（n 为草药种类数，m 为总时间）。空间复杂度是 O(m)。由于数据保证了 n 和 m 的乘积在可接受范围，完全背包可以直接通过。