Posted on 2009-07-01 10:32
Hero 閱讀(146)
評論(0) 編輯 收藏 引用 所屬分類:
代碼如詩－－ACM
1 //1039 Accepted 250 9660 1046 C++
2
3 //動態規劃
4 /*
5 dp[i][j][k]表示在前i個怪物中，在體力消耗不超過j的情況下，選出不超過k個怪物
6 殺死它們所能得到的最大經驗
7
8 dp[i][j][k] = fmax( dp[i-1][j][k], dp[i-1][j-w[i]][k-1]+v[i] ) ;
9 不選第i個怪物 選擇第i個怪物
10
11 順序動歸，每一個怪物都有選與不選兩種選擇
12 */
13 #include <iostream>
14 using namespace std ;
15
16 int inn, inm, ink, ins ;
17
18 int w[200] ;
19 int v[200] ;
20 int dp[110][110][110] ;
21
22 int fmax( int a, int b )
23 {
24 return a > b ? a : b ;
25 }
26
27 int main()
28 {
29 while( cin >> inn >> inm >> ink >> ins )
30 {
31 for( int k=1; k<=ink; k++ )
32 {
33 cin >> v[k] >> w[k] ;
34 }
35
36 memset( dp, 0, sizeof(dp) ) ;
37
38 for( int k=1; k<=ins; k++ )
39 {
40 for( int j=0; j<=inm; j++ )
41 {
42 if( j >= w[1] )
43 {
44 dp[1][j][k] = v[1] ;
45 }
46 }
47 }
48
49 for( int i=2; i<=ink; i++ )
50 {
51 for( int k=1; k<=ins; k++ )
52 {
53 for( int j=0; j<=inm; j++ )
54 {
55 if( j >= w[i] )
56 {
57 dp[i][j][k] = fmax( dp[i-1][j][k], dp[i-1][j-w[i]][k-1]+v[i] ) ;
58 }
59 else
60 {
61 dp[i][j][k] = dp[i-1][j][k] ;
62 }
63 }
64 }
65 }
66
67 int ans = -1 ;
68 for( int j=0; j<=inm; j++ )
69 {
70 if( dp[ink][j][ins] >= inn )
71 {
72 ans = j ; break ;
73 }
74 }
75
76 if( ans < 0 )
77 printf( "%d\n", ans ) ;
78 else
79 printf( "%d\n", inm-ans ) ;
80 }
81 return 0 ;
82 }