HDU 2159 FATE （DP 二维费用背包）

题意：中文题不详述。

思路：二维背包，dp[i][h]表示当前忍耐值为i的情况下，杀了h个怪得到的最大经验值，状态转移方程：

dp[i][h] = max(dp[i][h],dp[i-a[j].toler][h-1]+a[j].exper) ;

 1 //2159
 2 #include <stdio.h>
 3 #include <string.h>
 4 #include <iostream>
 5 
 6 using namespace std ;
 7 
 8 struct node
 9 {
10     int exper ;
11     int toler ;
12 }a[110] ;
13 
14 int dp[110][110] ;
15 
16 int main()
17 {
18     int n,m,k,s ;
19     while(~scanf("%d %d %d %d",&n,&m,&k,&s))
20     {
21         for(int i = 1 ; i <= k ; i++)
22             scanf("%d %d",&a[i].exper,&a[i].toler) ;
23         memset(dp,0,sizeof(dp)) ;
24         int ans = -1 ;
25         for(int i = 1 ; i <= m ; i++)//当前忍耐度下得到的最多经验
26         {
27             for(int j = 1 ; j <= k ; j++)
28             {
29                 for(int h = 1 ; h <= s ; h++)
30                     if(i >= a[j].toler)
31                     dp[i][h] = max(dp[i][h],dp[i-a[j].toler][h-1]+a[j].exper) ;
32             }
33             if(dp[i][s] >= n)
34             {
35                 ans = m-i ;
36                 break;
37             }
38         }
39         printf("%d
",ans) ;
40     }
41     return 0 ;
42 }

View Code