Posted on 2009-03-14 19:13
Hero 閱讀(117)
評論(0) 編輯 收藏 引用 所屬分類:
代碼如詩－－ACM
1 //1008 Accepted 265 660 878 C++
2 #include <stdio.h>
3 #include <stdlib.h>
4 #include <string.h>
5
6 int oo = 10000000 ;
7 const int size = 150000 ;
8 int dp[size] ;
9
10 int inn, inm ;
11
12 int fmin( int a, int b )
13 {
14 return a < b ? a : b ;
15 }
16
17 int main()
18 {
19 while( scanf( "%d", &inn ) != EOF )
20 {
21 int val[20], num[20] ; int total = 0 ;
22 for( int i=1; i<=inn; i++ )
23 scanf( "%d %d", &val[i], &num[i] ) ;
24 scanf( "%d", &inm ) ;
25
26 for( int i=0; i<=20100; i++ ) dp[i] = oo ;
27 dp[0] = 0 ;
28
29 for( int i=1; i<=inn; i++ )
30 {
31 total += val[i] * num[i] ;
32 int limit = fmin( inm, total ) ;
33 for( int k=1; k<=num[i]; k++ )
34 {
35 for( int j=0; j<=limit; j++ )
36 {
37 if( j-val[i] >= 0 )
38 dp[j] = fmin( dp[j], dp[j-val[i]]+1 ) ;
39 else
40 dp[j] = dp[j] ;
41 }
42 }
43 }
44
45 if( dp[inm] != oo ) printf( "%d\n", dp[inm] ) ;
46 else printf( "-1\n" ) ;
47 }
48 return 0 ;
49 }