【算法分析】

【算法分析】

首先我們要先讀懂題意，可能有部分同學在讀題的時候就有點難以理解。

我們首先來分析一個比較簡單的問題，現在一共有三堆石頭，每堆石子的數量分別是3，4，11。求合并成一堆石頭的最小得分。
對于這個問題，只有兩種選擇：
前兩堆石頭合并再和第三堆石頭合并。
3+4=7 ——> 7 石堆變為（7， 11）
7+11=18——>18 石堆變為（18）
cost=7+18=25
后兩堆石頭合并再和第一堆石頭合并。
4+11=15——>15 石堆變為（3，15）
3+15=18——>18 石堆變為（18）
cost=15+18=33

易看出先合并前兩堆的石子的花費比較小，不同的合并方式會造成不同的得分。同時可以發現這兩種方法最后一次的得分就是石頭的總數。

狀態定義：s[i]表示前i堆石頭的價值總和，第i堆到第j堆石子數量加和為s[j]-s[i-1]。

f[i][j]表示把第i堆到第j堆的石頭合并成一堆的最優值。將第i堆到第i堆合并為1堆，不需要操作，不會產生得分，得分為0。因此：f[i][i]=0。

集合：將第i到第j堆石子合并為一堆的方案 在合為一堆時，第i到第j堆石子一定已經通過某種方案合并成了相鄰的左右兩堆。然后這兩堆合為一堆，這次合并產生的得分為第i到第j堆石子數量的加和s[j]-s[i-1]。設一個k∈[i,j）； ?

? ? for (i=n-1; i>=1; i--)
? ? ? for (j=i+1; j<=n; j++)
? ? ? ? for (k=i; k<=j-1; k++)
? ? ? ? ? f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]+s[j]-s[i-1]);

最后輸出第1堆到第n堆合并能得到的最小分數f[1][n]

【參考代碼】

#include<bits/stdc++.h>
using namespace std;
int f[101][101], s[101], n,i,j,k,x;
int main() {scanf("%d",&n);for (i=1; i<=n; i++) {scanf("%d",&x);s[i]=s[i-1]+x;}memset(f,0x3f,sizeof(f));  for (i=1; i<=n; i++) f[i][i]=0;   for (i=n-1; i>=1; i--)for (j=i+1; j<=n; j++)for (k=i; k<=j-1; k++)f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]+s[j]-s[i-1]);printf("%d\n",f[1][n]);return 0;
}