疯狂的采药

· · 题解

这道题就是一个完全背包问题

T,采药的限制时间 M,采药的个数 接着的M行表示采药的时间和价值，完全可以看成T,背包空间 M,物品个数 时间 物品的体积wi  价值 物品的价值ci 一道典型的完全背包问题.

但是.......

注意看数据说明

对于30%的数据， M <= 1000 ；

对于全部的数据， M <= 10000，且M*T<10000000(别数了，7个0) 。

要是你开那么大的数组直接炸了！

所以我们需要优化空间和时间。

    不难看出，我们每次都在对j进行修改，j表示前i个物品装入背包后的剩余体积，那我们把i给不要怎么样?

    那就可以这样写:dp[j]=max(dp[j-w[i]]+c[i],dp[j])也就是往背包里不停地加物品,貌似也没什么问题,反正物品就是无限个的，只要加的物品体积不超过背包体积就行,既然少了一维，看见复杂度也随之减少。

    我们可以直接枚举1~m种物品,在让j从0到t给i加个限制,也就是: 
    for(int i=1;i<=m;i++)
        for(int j=0;j<=t;j++) 
    最后直接在双层for循环里加
            if(w[i]<=j)//必须小，不然减不了（装不下），还会RE
                dp[j]=max(dp[j],dp[j-w[i]]+c[i]);

你是否明白了?

既然一维且双重for那就不怕那数据了

终极AC代码如下:
#include <bits/stdc++.h>
using namespace std;
long long m,n,w[100010],c[100010],dp[100010];
int main(){
  cin>>m>>n;
  for(int i=1;i<=n;i++){//不想说了。。。
        cin>>w[i]>>c[i];
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(j>=w[i]){//限制的体积能够装
                dp[j]=max(dp[j],dp[j-w[i]]+c[i]);//那就毛起往里面塞就行
            }
        }
    }
    cout<<dp[m];//愉快地输出
    while(1);//防那啥
    return 0;
}//写题解不易啊，求过鸭