题解 P1616 【疯狂的采药】

完全背包模板题。 考虑动态规划。原问题最重要的参数是草药的数目和采药的时间，那么我们很容易想到定义状态$dp_{i,j}$，表示在$j$时间内，采前$i$种草药能够取得的最大价值。 关键是状态转移方程。 对于每一草药$i$，都有采和不采两种状态。设当前采药时间上限为$j$，那么： 1. 采第$i$种草药，那么用来采前$i-1$种草药的时间只剩$j-a_i$了，前$i-1$种草药能取得的最大价值就是$dp_{i-1,j-a_i}$。再加上第$i$种草药的价值，总共就是$dp_{i-1,j-a_i}+b_i$。然而每种草药可以采摘无限多次，所以我们要使用更新过的值$dp_{i,j-a_i}+b_i$。 2. 不采第$i$种草药，那么在当前的草药上就不需要花费任何时间，当前草药就完全是废的，没用。只需考虑前$i-1$种草药。最大价值为$dp_{i-1,j}$。 由于每次状态转移都只需要用到上一种草药更新的值，所以可以考虑把$dp$数组的第一维压掉。最后的状态转移方程：`dp[j]=max(dp[j],dp[j-a[i]]+b[i])` 那么就可以上代码了。 ``` #include<bits/stdc++.h> #define int long long//不开ll见祖宗 using namespace std; int n,m; int a[10001]; int b[10001]; int dp[10000001]; signed main(){ cin>>m>>n; for(int i=1;i<=n;i++) cin>>a[i]>>b[i]; for(int i=1;i<=n;i++) for(int j=a[i];j<=m;j++)//必须要有足够的时间采当前草药，所以从a[i]开始循环。 dp[j]=max(dp[j],dp[j-a[i]]+b[i]); cout<<dp[m]<<endl; return 0; } ```