NO IMAGE

題目大意:假設有一排n堆石子,每堆石子有若干個小石子,要求將它們合併成一堆,需要花費的最小代價。而且每次合併只能將相鄰的兩堆合併,合併的代價是兩堆石子的重量之和。

題目分析:因為不能合併有間隔的石子堆,所以這不是一道哈夫曼樹的例子(哈夫曼樹:利用貪心演算法,每次合併重量最小的兩堆石子)。

通過分解子問題,我們可以發現,當只有一堆石子時,合併代價為0;

當有兩堆石子時,合併代價是兩堆石子重量之和;

當有三堆石子時,合併代價是前兩個合併,再和第三個合併;或者後兩個先合併,再和第一個合併。這兩種方法取一個最小值;

那麼,由此得知:我們可以令dp[i][j]表示合併第i堆石子,到第j堆石子花費的最小值。

dp[i][j]  = min(dp[i][k],dp[k 1][j]) sum[i][j] ,   其中sum[i][j]表示第i堆石子到第j堆石子之間所有石子的重量和

上式解釋:要合併第i堆石子-第j堆石子,我們可以分為三步,第一步合併第i堆石子-第k堆石子,第二步合併第k 1堆石子-第j堆石子,第三步,將合併的兩堆石子再合併,代價是它們之間所有的石子重量和。其中,k可以從i取到j-1.

當i=j時,也就是隻有一堆石子,dp[i][j] 自然就是0.

至此,我們可以畫出以下的狀態轉移表,自底向上求解,將前一步的解儲存在一個表中:

i|j

0

1

2

3

4

0

0

3

11

?

?

1

0

5

?

?

2

0

7

?

3

0

9

4

0

上表是例子:1 2 3 4 的一個狀態表。 其中dp[i][j]中,j必須大於i,所有左下部分為空。dp[i][j] = 0 (i==j) 所以對角線上元素為0 然後我們計算的是 dp[0][1],dp[1][2],dp[2][3],dp[3][4], 然後是基於前面的結果計算dp[0][2],dp[1][3],dp[2][4]……

所以計算順序是按照斜對角線的方向,慢慢往上計算。我們可以發現,每一斜列的j-i都是一個定值,比如dp[0][0],dp[1][1],dp[2][2],dp[3][3]的j-i=0.  dp[0][1],dp[1][2],dp[2][3],dp[3][4]的j-i=1. dp[0][2],dp[1][3],dp[2][4]的j-i=2……

我們可以按照j-i的值作為迴圈的變數,記作l. (l=0, l=1, l=2, l=3……)

程式碼展示:

#include <iostream>
#include <string.h>
#include <algorithm>
using namespace std;
int main(){
int n;
cin>>n;
int num[n];
long long sum[n];
memset(sum,0,sizeof(sum));
for(int i=0;i<n;i  ){
cin>>num[i];
if(i==0)
sum[i] = num[i];
else
sum[i] = sum[i-1]   num[i];
}
long long dp[n][n];
memset(dp,0,sizeof(dp));
long long temp = 0;
for(int l=1;l<n;l  ){    //每一條斜線代表的i與j的差值
for(int i=0;i<n&&i l<n;i  ){
long long min_value = dp[i][i] dp[i 1][i l];
for(int k=i 1;k<=i l-1;k  ){
temp = dp[i][k] dp[k 1][i l];
if(temp<min_value)
min_value = temp;
}
if(i>0)
dp[i][i l] = min_value   (sum[i l] - sum[i-1]);
else
dp[i][i l] = min_value   sum[l];
}
}
cout<<dp[0][n-1]<<endl;
return 0;
}

為了使最後一組資料不超時,我們可以用sum[]一維陣列代替二維陣列,即用sum[i]儲存前i個元素之和,這樣第i個元素到第j個元素的和可以表示為sum[j] – sum[i-1].