Posted on 2009-06-05 15:36
Hero 閱讀(106)
評論(0) 編輯 收藏 引用 所屬分類:
代碼如詩－－ACM
1 //1216 Accepted 1468 17340 808 C++
2 /*
3 動態規劃
4 直接繼承 間接繼承
5 dp[i][0] = fmax( dp[i-1][0]+data[i][0], dp[i-2][1]+data[i][0] ) ;
6 dp[i][1] = fmax( dp[i-1][1]+data[i][1], dp[i-2][0]+data[i][1] ) ;
7
8 其實就是保存了所有的解空間
9 */
10 #include <iostream>
11 #include <string>
12 #include <algorithm>
13 using namespace std ;
14
15 const int size = 2000 ;
16
17 int tnum ;
18 int inn ;
19
20 int data[1100000][2] ;
21 int dp[1100000][2] ;
22
23 int fmax( int a, int b )
24 {
25 return a > b ? a : b ;
26 }
27 int main()
28 {
29 while( cin >> tnum )
30 {
31 while( tnum -- )
32 {
33 cin >> inn ;
34
35 for( int i=1; i<=inn; i++ ) scanf( "%d", &data[i][0] ) ;
36 for( int i=1; i<=inn; i++ ) scanf( "%d", &data[i][1] ) ;
37
38 dp[0][0] = dp[0][1] = 0 ;
39 dp[1][0] = data[1][0] ;
40 dp[1][1] = data[1][1] ;
41
42 for( int i=2; i<=inn; i++ )
43 {
44 dp[i][0] = fmax( dp[i-1][0]+data[i][0], dp[i-2][1]+data[i][0] ) ;
45 dp[i][1] = fmax( dp[i-1][1]+data[i][1], dp[i-2][0]+data[i][1] ) ;
46 }
47
48 printf( "%d\n", fmax(dp[inn][0], dp[inn][1]) ) ;
49 }
50 }
51
52 return 0 ;
53 }