ConanKIDの小窝

ConanKIDの小窝

题解 P1616 【疯狂的采药】

posted on 2020-08-30 13:51:09 | under 题解 |

完全背包模板题。

考虑动态规划。原问题最重要的参数是草药的数目和采药的时间,那么我们很容易想到定义状态$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;
}