hdu 2159 FATE（二维费用完全背包）

看题目请点这里

题意：

中文题不解释。

代码：

#include<iostream>using namespace std;int main(){int n,m,k,s,i,j,l,ans,a[101],b[101],dp[101][101];while(scanf("%d %d %d %d",&n,&m,&k,&s)!=EOF){for(i=0;i<k;i++){scanf("%d %d",a+i,b+i);}memset(dp,0,sizeof(dp));ans=-1;for(i=0;i<k;i++){for(j=b[i];j<=m;j++)   //j表示用掉的忍耐度{for(l=1;l<=s;l++)   //l表示杀怪数{if(dp[j][l]<dp[j-b[i]][l-1]+a[i] ){dp[j][l]=dp[j-b[i]][l-1]+a[i];}if(dp[j][l]>=n && ans < m-j)   //找剩余的最大忍耐度{ans=m-j;}}}}printf("%d\n",ans);}return 0;}