Posted on 2009-03-13 16:54
Hero 閱讀(121)
評論(0) 編輯 收藏 引用 所屬分類:
代碼如詩－－ACM
1 //1007 Accepted 31 120 824 C++
2 #include <stdio.h>
3 #include <stdlib.h>
4 #include <string.h>
5 const int oo = 100000000 ;
6 const int size = 110 ;
7 int data[size] ;
8 int dp[size][size] ;
9
10 int inn ;
11
12 int fmin( int a, int b )
13 {
14 return a < b ? a : b ;
15 }
16
17 int DFS( int sn, int en )
18 {
19 if( abs(en-sn) < 2 ) return 0 ;
20 if( dp[sn][en] != -1 ) return dp[sn][en] ;
21
22 for( int mid=sn+1; mid<=en-1; mid++ )
23 {
24 if( -1 == dp[sn][en] )
25 dp[sn][en] = DFS(sn,mid)+DFS(mid,en)+(data[sn]*data[mid]*data[en]) ;
26 else
27 dp[sn][en] = fmin( dp[sn][en], DFS(sn,mid)+DFS(mid,en)+(data[sn]*data[mid]*data[en])) ;
28 }
29
30 return dp[sn][en] ;
31 }
32
33 int main1()
34 {
35 while( scanf( "%d", &inn ) != EOF )
36 {
37 for( int i=1; i<=inn; i++ ) scanf( "%d", &data[i] ) ;
38
39 memset( dp, -1, sizeof(dp) ) ;
40
41 printf( "%d\n", DFS(1, inn) ) ;
42 }
43 return 0 ;
44 }
45
46 //1007 Accepted 15 120 1393 C++
47 int main()
48 {
49 while( scanf( "%d", &inn ) != EOF )
50 {
51 for( int i=1; i<=inn; i++ ) scanf( "%d", &data[i] ) ;
52
53 memset( dp, 0, sizeof(dp) ) ;
54
55 for( int diff=2; diff<=inn-1; diff++ )//漸進式DP
56 {
57 for( int sn=1; sn<=inn; sn++ )
58 {
59 int en = sn + diff ; if( en > inn ) break ;
60 dp[sn][en] = oo ;
61 for( int mid=sn+1; mid<=en-1; mid++ )
62 {
63 dp[sn][en] = fmin( dp[sn][en], dp[sn][mid]+dp[mid][en]+data[sn]*data[mid]*data[en] ) ;
64 }
65 }
66 }
67
68 printf( "%d\n", dp[1][inn] ) ;
69 }
70
71 return 0 ;
72 }