hdu 2159 FATE

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

思路：二维完全背包，状态转移方程为: f[j][l]=max(f[j][l],f[j-b[i]][l-1]+w[i]); a[i]表示杀死第i个怪所得的经验值,b[i]表示消耗的忍耐度

 1 #include<stdlib.h>
 2 #include<time.h>
 3 #include <cstdio>  
 4 #include <cstring>  
 5 #include <cmath>  
 6 #include <cstdlib>  
 7 #include <ctime>  
 8 #include <iostream>  
 9 #include <algorithm>  
10 #include <vector>  
11 #include <queue>  
12 #include <map>  
13 #include <set>  
14 #include <string>  
15 using namespace std;
16 
17 
18 int dp[100][100];
19 
20 int main()
21 {
22     int a[100],b[100];
23     int n,m,k,s;
24     int i,j,l,locate,flag;
25     while(scanf("%d %d %d %d",&n,&m,&k,&s)!=EOF)
26     {
27         memset(dp,0,sizeof(dp));
28         for(i=0;i<k;i++)
29         {
30             scanf("%d %d",&a[i],&b[i]);
31         }
32         for(i=0;i<k;i++)
33         {
34             for(j=b[i];j<=m;j++)
35             {
36                 for(l=1;l<=s;l++)
37                     dp[j][l]=max(dp[j][l],dp[j-b[i]][l-1]+a[i]);
38             }
39         }
40         flag=0;
41         for(i=0;i<=m;i++)
42         {
43             if(flag)
44                 break;
45             for(j=0;j<=s;j++)
46             {
47                 if(dp[i][j]>=n)
48                 {
49                     locate=i;
50                     flag=1;
51                     break;
52                 }
53             }
54         }
55         if(flag)
56             printf("%d
",m-locate);
57         else
58         printf("-1
");
59     }
60     return 0;
61 }