洛谷 P1616 疯狂的采药

嗯...

 

题目链接：https://www.luogu.org/problemnew/show/P1616

 

首先这道题的正解是：完全背包。

 

首先，背包？

　　背包的种类：

　　背包分为01背包，多重背包以及完全背包这三种基本模型，其他的背包问题都是从这3种背包中延申出来的。

　　思路介绍：本题修改自 <P1048>采药-传送门。

　　此题是什么背包？

　　看到题面的第一眼：[无限量]的采摘药,这便是完全背包了。

　　完全背包的模板题面是这样的：设有n种物品，每种物品有一个重量及一个价值。但每种物品的数量是无限的，同时有一个背包，

　　最大载重量为M，今从n种物品中选取若干件(同一种物品可以无限选取)，使其重量的和小于等于M，而价值的和为最大。

　　大家看到本题与上面的描述中共同拥有的一个特点，每种物品无限个。那么我们只需要将01背包的代码进行略微修改即可。（01转多重也只是略微修改）

 

其次，代码？

　　完全背包代码段：

for(int i = 1;i <= n; i++)
    for(int j = w[i]; j <= V; j++)
        dp[j] = max(dp[j], f[j - w[i]] + c[i]);

　　01背包代码段：

for(int i = 1; i <= n; i++)
    for(int j = m; j >= s[i]; j--)
        dp[j] = max( dp[j], dp[j- s[i]] + v[i]);

　　区别？

　　将逆序改成顺序，因为我们需要递推的是当前药品更新后发生改变的状态。所以要顺序求解。

 

AC代码：

#include<cstdio>
#include<iostream> 

using namespace std;

const int maxn = 100005;

int ti[maxn], dp[maxn], val[maxn];
int ans;

int main(){
    int t, m;
    scanf("%d%d", &t, &m);
    for(int i = 1; i <= m; i++)
        scanf("%d%d", &ti[i], &val[i]);
    for(int i = 1; i <= m; i++){
        for(int j = ti[i]; j <= t; j++){
            dp[j] = max(dp[j - ti[i]] + val[i], dp[j]);
        }
    }
    for(int i = 1; i <= t; i++)
        ans = max(ans, dp[i]);
    printf("%d\n", ans);
    return 0;
}