CODE[VS] 天梯 1048 石子歸并

2019-11-09 20:43:56

字體：大中小

來源：轉載

供稿：網友

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 1 1 4

樣例輸出 Sample Output

思路：

動規轉移方程: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]; } } } }