題目
設有 N 堆石子排成一排，其編號為 1,2,3,…,N。
每堆石子有一定的質量，可以用一個整數來描述，現在要將這 N 堆石子合并成為一堆。
每次只能合并相鄰的兩堆，合并的代價為這兩堆石子的質量之和，合并后與這兩堆石子相鄰的石子將和新堆相鄰，合并時由于選擇的順序不同，合并的總代價也不相同。
例如有 4 堆石子分別為 1 3 5 2， 我們可以先合并 1、2堆，代價為 4，得到 4 5 2， 又合并 1、2堆，代價為 9，得到 9 2 ，再合并得到 11，總代價為 4+9+11=24；
如果第二步是先合并 2、3 堆，則代價為 7，得到 4 7，最后一次合并代價為 11，總代價為 4+7+11=22。
問題是：找出一種合理的方法，使總的代價最小，輸出最小代價。
輸入格式
第一行一個數 N 表示石子的堆數 N。
第二行 N 個數，表示每堆石子的質量(均不超過 1000)。
輸出格式
輸出一個整數，表示最小代價。
數據范圍
1≤N≤300
輸入樣例：
輸出樣例：
解題思路：
按區間從短到長依次枚舉，求區間中石子合并的最小代價并記錄在f數組中
例如
區間長度len=2時得到
f[1][2] = 4，f[2][3] = 8，f[3][4] = 7
在區間長度len=3時根據f[l][r]=min(f[l][r],f[l][k]+f[k+1][r]+s[r]-s[l-1]);就可以得到
f[1][3]=f[1][2]+f[3][3]+(s[3]-s[0])=13
ps：區間長度遞增的原因是區間長度長的利用到了區間長度小的數值
程序代碼
#include<bits/stdc++.h> const int N=1010; int f[N][N];//表示區間 int s[N]; //求前綴和 int a; using namespace std; int main() { cin>>a; for(int i=1;i<=a;i++)cin>>s[i]; for(int i=1;i<=a;i++)s[i]+=s[i-1];//求前綴和，使得下標之差就是區間的元素之和 for(int len=2;len<=a;len++)//len代表區間的長度，區間的長度遞增 { for(int i=1;i+len-1<=a;i++)//例如，i=1，len=2時 i+len-1=2，1到2即表示區間長度為2 { int l=i,r=i+len-1; f[l][r]=0x3f3f3f3f; for(int k=l;k<r;k++)//k用來切割區間 { f[l][r]=min(f[l][r],f[l][k]+f[k+1][r]+s[r]-s[l-1]); //區間從左到右依次分割求理想的最小值 } //s[r]-s[l-1]為最后一下合并區間內的石子需要的體力為區間內所有石子的和 } } cout<<f[1][a];//輸出1到a區間的最小和，就是答案 }
| 
