Posted on 2008-08-20 21:26
Hero 閱讀(345)
評(píng)論(1) 編輯 收藏 引用 所屬分類(lèi):
代碼如詩(shī)－－ACM
1 //Accepted 100 From 054100526－P1303 CPP
2
3 //一個(gè)著名的定理是這樣的：最長(zhǎng)上升序列的長(zhǎng)度等于不上升序列的最小分劃
4 //（即將平面上的點(diǎn)分劃成盡可能少的不相交的不上升序列）
5
6 //特殊數(shù)據(jù)
7 /*
8 關(guān)鍵是第二問(wèn)，如果每次都求最靠前的最長(zhǎng)下降序列再剔除，有些數(shù)據(jù)是過(guò)不了的，比如
9 12 7 11 6 10 5 9
10 這樣得出的答案是12 11 10 5、7 6、9（3套系統(tǒng)）
11 正確答案12 11 10 9、7 6 5（2套系統(tǒng)）
12 */
13 #include <stdio.h>
14 #include <stdlib.h>
15 #include <string.h>
16
17 const int size = 500 ;
18 int data[size] ;
19
20 int dp[size] ;
21
22 int fmax( int a, int b )
23 {
24 return a > b ? a : b ;
25 }
26
27 int main()
28 {
29 memset( data, 0, sizeof(data) ) ;
30 int cnt = 0 ; char ch ;
31
32 while( scanf( "%d", &data[++cnt] ) != EOF )
33 {
34 ch = getchar() ; //printf( "ch == %c\n", ch ) ;
35 if( '\n' == ch ) break ;
36 if( ch != ',' ) break ;
37 }
38
39 while( 0 == data[cnt] ) cnt-- ;
40
41 dp[1] = 1 ;
42 for( int i=2; i<=cnt; i++ )
43 {
44 dp[i] = 1 ;
45 for( int j=1; j<i; j++ )
46 {
47 if( data[j]>=data[i] ) dp[i] = fmax( dp[i], dp[j]+1 ) ;
48 }
49 }//最長(zhǎng)不下降序列
50
51 int maxlen = -1 ;
52
53 for( int i=1; i<=cnt; i++ ) maxlen = fmax( maxlen, dp[i] ) ;
54 printf( "%d,", maxlen ) ;
55
56 dp[1] = 1 ;
57 for( int i=2; i<=cnt; i++ )
58 {
59 dp[i] = 1 ;
60 for( int j=1; j<i; j++ )
61 {
62 if( data[j]<data[i] ) dp[i] = fmax( dp[i], dp[j]+1 ) ;
63 }
64 }//最長(zhǎng)上升序列==不下降序列的最小分劃
65
66 maxlen = -1 ;
67
68 for( int i=1; i<=cnt; i++ ) maxlen = fmax( maxlen, dp[i] ) ;
69 printf( "%d\n", maxlen-1 ) ;
70
71 return 0 ;
72 }