题解 P1616 【疯狂的采药】

jimmylijiaji · 2017-08-08 14:23:31 · 题解

简单背包问题 完全背包 注意使用滚动数组或者一维数组 不然会爆空间

#include<cstdio>
#include<algorithm>
using namespace std;
const int N = 10005;//N M代表含义在原题中找
const int M = 100005;
int n,m;
int t[N],v[N];//t代表取每一株的时间 v代表每一株的价值
int f[M];//一维数组
int main()
{
    int i,j;
    scanf("%d%d",&m,&n);
    for(i=1;i<=n;i++)
    {
        scanf("%d%d",&t[i],&v[i]);
    }
    f[0]=0;
    for(i=1;i<=n;i++)
    {
        for(j=t[i];j<=m;j++)
            f[j]=max(f[j],f[j-t[i]]+v[i]);//更新f[j] 动态转移方程同 “f[i][j] = max(f[i-1][j],f[i][j-t[i]]+v[i])”
    }
    int ans=0;
    for(j=0;j<=m;j++)
        ans=max(ans,f[j]);//寻找答案 输出
    printf("%d\n",ans);
    return 0;
}