1048 石子歸并
?
時間限制: 1 s
空間限制: 128000 KB
題目等級 : 黃金 Gold
題目描述 Description
有n堆石子排成一列，每堆石子有一個重量w[i], 每次合并可以合并相鄰的兩堆石子，一次合并的代價為兩堆石子的重量和w[i]+w[i+1]。問安排怎樣的合并順序，能夠使得總合并代價達到最小。
輸入描述 Input Description
第一行一個整數n（n<=100）
第二行n個整數w1,w2...wn ?(wi <= 100)
輸出描述 Output Description
一個整數表示最小合并代價
樣例輸入 Sample Input
4
4 1 1 4
樣例輸出 Sample Output
18
數據范圍及提示 Data Size & Hint
分類標簽 Tags 點此展開
一定要注意i,j，k在數組中的取值！
1 #include<iostream> 2 #include<cstdio> 3 #include<cmath> 4 #include<cstring> 5 using namespace std; 6 const int MAXN=101; 7 int a[MAXN]; 8 int f[MAXN][MAXN]; 9 int main() 10 { 11 memset(f,0x3f,sizeof(f)); 12 int n; 13 scanf("%d",&n); 14 for(int i=1;i<=n;i++) 15 f[i][i]=0; 16 for(int i=1;i<=n;i++)cin>>a[i]; 17 for(int i=2;i<=n;i++)a[i]=a[i]+a[i-1]; 18 for(int i=n;i>=1;i--) 19 for(int j=i+1;j<=n;j++) 20 for(int k=i;k<j;k++) 21 f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]+a[j]-a[i-1]); 22 printf("%d",f[1][n]); 23 return 0; 24 }
?
)
環境配置)
)
