hdu 2159 FATE (二维完全背包)

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

思路: dp[j][k] 代表消耗耐久度j,干掉k个敌人获得的经验值。

状态转移方程为: dp[j][k] = max(dp[j][k],dp[j-b[i]][k-1]+a[i]);

保存下当获得经验值可以升级时,维护下最小的耐久消耗

实现代码:

#include<bits/stdc++.h>
using namespace std;
const int inf = 0x3f3f3f3f;
int dp[][],a[],b[]; int main()
{
int n,m,h,s;
while(cin>>n>>m>>h>>s){
for(int i = ;i <= h;i ++){
cin>>a[i]>>b[i];
}
memset(dp,,sizeof(dp));
int ans = inf;
for(int i = ;i <= h;i ++){
for(int j = b[i];j <= m;j ++){
for(int k = ;k <= s;k ++){
dp[j][k] = max(dp[j][k],dp[j-b[i]][k-]+a[i]);
if(dp[j][k] >= n) ans = min(ans,j);
}
}
}
if(ans == inf) cout<<"-1"<<endl;
else cout<<m-ans<<endl;
}
}
上一篇:sencha touch中按钮的ui配置选项值及使用效果


下一篇:SELINUX设为Disable 影响java SSH工具包Jsch 0.1.49.jar的一个案例