首页 > 代码库 > hdu2159(二维完全背包)

hdu2159(二维完全背包)

 

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=2159

题意:打怪,还有最后一级,忍耐度有限m,问在杀怪数量上限为s的情况下能否获取n经验而通关,且忍耐度花越少越好。

分析:dp[i][j]表示打了数量为i花费忍耐度为j得到的最大经验值。

状态转移方程:dp[i][j]=max(dp[i][j],dp[i-1][j-w[i]]+p[i])

#include <cstdio>#include <cstring>#include <cmath>#include <iostream>#include <algorithm>#include <queue>#include <cstdlib>#include <vector>#include <set>#include <map>#define LL long long#define mod 1000000007#define inf 0x3f3f3f3f#define N 10010using namespace std;int dp[110][110],w[110],p[110];int main(){    int n,m,s,k;    while(scanf("%d%d%d%d",&n,&m,&k,&s)>0)    {        for(int i=1;i<=k;i++)scanf("%d%d",&p[i],&w[i]);        memset(dp,-1,sizeof(dp));        memset(dp[0],0,sizeof(dp[0]));        for(int i=1;i<=k;i++)        for(int j=w[i];j<=m;j++)        for(int k=s;k>0;k--)        {            if(dp[k-1][j-w[i]]!=-1)            dp[k][j]=max(dp[k][j],dp[k-1][j-w[i]]+p[i]);        }        int ans=-1;        for(int i=1;i<=s;i++)        for(int j=1;j<=m;j++)        if(dp[i][j]>=n)        {            ans=max(ans,m-j);break;        }        printf("%d\n",ans);    }}
View Code

 

hdu2159(二维完全背包)