链接：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;
}
}