Posted on 2008-09-10 19:02
Hero 閱讀(192)
評論(0) 編輯 收藏 引用 所屬分類:
代碼如詩－－ACM
1 //1717 Accepted 272K 47MS C++ 1048B PKU
2
3 //第一個標(biāo)號法程序--不斷更新當(dāng)前能取得的組合數(shù)的最小翻轉(zhuǎn)次數(shù)
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 )//如果當(dāng)前的值組合出來過
28 {
29 int turns = flag[k] ;//得到當(dāng)前組合數(shù)所需要的反轉(zhuǎn)次數(shù)
30 flag[k] = INF ;//由于要更新--當(dāng)前組合數(shù)不存在了
31
32 //更新操作--如果下一個dn可以得到的值k+indn所需的次數(shù)比當(dāng)前大--更新
33 //以dn為基準(zhǔn)--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 }//標(biāo)號法更新
39
40 //從中間開始向兩邊搜尋down可以翻轉(zhuǎn)最小次能夠得到的值
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 }