Posted on 2008-09-10 19:02
Hero 阅读(178)
评论(0) 编辑 收藏 引用 所属分类:
代码如诗－－ACM
1 //1717 Accepted 272K 47MS C++ 1048B PKU
2
3 //第一个标号法程序--不断更新当前能取得的组合数的最小翻转次数
4
5 #include <stdio.h>
6 #include <string.h>
7 #include <stdlib.h>
8
9 const int INF = 1e9 ;
10 const int size = 14000 ;
11
12 int flag[size+100] ;
13 int inn ;
14
15 void process()
16 {
17 flag[0] = 0 ;
18 for( int i=1; i<=size; i++ ) flag[i] = INF ;
19
20 int inup, indn ; int sum = 0 ;
21
22 for( int i=1; i<=inn; i++ )
23 {
24 scanf( "%d %d", &inup, &indn ) ; sum += ( inup+indn ) ;
25 for( int k=sum; k>=0; k-- )
26 {
27 if( flag[k] != INF )//如果当前的值组合出来过
28 {
29 int turns = flag[k] ;//得到当前组合数所需要的反转次数
30 flag[k] = INF ;//由于要更新--当前组合数不存在了
31
32 //更新操作--如果下一个dn可以得到的值k+indn所需的次数比当前大--更新
33 //以dn为基准--k+indn更新时不需要+1
34 if( flag[k+indn] > turns ) flag[k+indn] = turns ;
35 if( flag[k+inup] > turns+1 ) flag[k+inup] = turns+1 ;
36 }
37 }
38 }//标号法更新
39
40 //从中间开始向两边搜寻down可以翻转最小次能够得到的值
41 int i, j ;
42 for( i=sum/2,j=sum/2.0+0.5; INF==flag[i]&&INF==flag[j]; i--,j++ ) ;
43
44 printf( "%d\n", flag[i]<flag[j]? flag[i]:flag[j] ) ;
45 }
46
47 int main()
48 {
49 while( scanf( "%d", &inn ) != EOF )
50 {
51 //input() ;
52
53 process() ;
54
55 //output() ;
56 }
57
58 return 0 ;
59 }