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 10010
using namespace std;
int dp[][],w[],p[];
int main()
{
int n,m,s,k;
while(scanf("%d%d%d%d",&n,&m,&k,&s)>)
{
for(int i=;i<=k;i++)scanf("%d%d",&p[i],&w[i]);
memset(dp,-,sizeof(dp));
memset(dp[],,sizeof(dp[]));
for(int i=;i<=k;i++)
for(int j=w[i];j<=m;j++)
for(int k=s;k>;k--)
{
if(dp[k-][j-w[i]]!=-)
dp[k][j]=max(dp[k][j],dp[k-][j-w[i]]+p[i]);
}
int ans=-;
for(int i=;i<=s;i++)
for(int j=;j<=m;j++)
if(dp[i][j]>=n)
{
ans=max(ans,m-j);break;
}
printf("%d\n",ans);
}
}
上一篇:Android手机与计算机间的”信任关系”


下一篇:Python多进程操作同一个文件,文件锁问题