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
思路：
動規 轉移方程:f[i][j] = max(f[i][j] , f[i][k]+f[k+1][j]+sum[i][j])
代碼
#include<iostream>#include<string.h>#include<math.h>#include<algorithm>#include<stdio.h> using namespace std;int f[101][101];int sum[101][101];int INF = 0x7fffffff;//這里代表int最大值，即最大移動石子的最少質量必須少于這個，不然超int int main(){ int n; scanf("%d",&n); int stone[101]; for(int i = 1;i<=n;i++){ scanf("%d",&stone[i]); } //求出任意間石頭總數，表示當前歸并需要累加的值。如[1][3]表示，在歸并1-3堆石子時，從第二步到第三步需要移動的石頭數 for(int i = 1;i<=n;i++){ for(int j=i;j<=n;j++){ sum[i][j] = sum[i][j-1]+stone[j];//初始化 } } for(int len = 2;len<=n;len++){ for(int i = 1;i<=n-len+1;i++){ int k = i+len-1; f[i][k] = INF; //設置i-k最大，然后取最小 for(int j = i;j<=k-1;j++){//前一步的結果要加上本步的結果，選出最佳 .所以這里要再退前一步 if(f[i][k]>f[i][j]+f[j+1][k]+sum[i][k]){ f[i][k] = f[i][j]+f[j+1][k]+sum[i][k]; } } } }新聞熱點
疑難解答
