Posted on 2008-09-01 23:23
Hero 阅读(212)
评论(0) 编辑 收藏 引用 所属分类:
代码如诗－－ACM
1 //PKU 1742 Accepted 1484K 985MS G++ 1424B coin
2
3 //区间动态规划--可重复币值的分割
4
5 #include <stdio.h>
6 #include <stdlib.h>
7 #include <string.h>
8
9 const int size = 100100 ;
10
11 struct COIN
12 {
13 int val ;
14 int num ;
15 };
16 struct COIN coin[110] ;
17
18 struct NODE
19 {
20 int cval ;//当前值是的最后一个组成硬币是多少
21 int cnum ;//该硬币已经用了多少个
22 };
23 struct NODE node[size] ;
24
25 int flag[size] ;//记录硬币是否已经找过
26
27 int inn, ink ;
28
29 void input()
30 {
31 for( int i=1; i<=inn; i++ ) scanf( "%d", &coin[i].val ) ;
32
33 for( int i=1; i<=inn; i++ ) scanf( "%d", &coin[i].num ) ;
34 }
35
36 void process()
37 {
38 for( int i=0; i<size; i++ )
39 {
40 node[i].cnum = node[i].cval = flag[i] = 0 ;
41 }
42
43 flag[0] = 1 ;
44
45 int max = 0 ; int sum = 0 ; int temp ;
46 for( int i=1; i<=inn; i++ )
47 {//
48 max += coin[i].val * coin[i].num ;
49 if( max > ink ) max = ink ;
50
51 for( int c=coin[i].val; c<=max; c++ )
52 {
53 if( flag[c] ) continue ;
54
55 temp = c - coin[i].val ;//temp为当前c的前驱
56 if( flag[temp] )
57 {
58 if( node[temp].cval == coin[i].val )
59 {
60 if( node[temp].cnum < coin[i].num )
61 {
62 flag[c] = 1 ; sum++ ; node[c].cval = coin[i].val ; node[c].cnum = node[temp].cnum+1 ;
63 }
64 }
65 else
66 {
67 flag[c] = 1 ; sum++ ; node[c].cval = coin[i].val ; node[c].cnum = 1 ;
68 }
69 }
70 }
71 }
72
73 printf( "%d\n", sum ) ;
74 }
75
76 int main()
77 {
78 //freopen( "in.txt", "r", stdin ) ;
79
80 while( scanf( "%d %d", &inn, &ink ) != EOF && (inn||ink) )
81 {
82 input() ;
83
84 process() ;
85
86 //output() ;
87 }
88
89 return 0 ;
90 }