來源藍橋杯：算法提高 石子合并

      很明顯的區間DP，d(i, j)表示取第i堆到第j堆石子最少花費，轉移方程d(i, j) = min(d(i, k) + d(k+1, j)) +  sum[j] - sum[i].

       四邊形a <= b < c <= d，有w(b, c) <= w(a, d)滿足決策單調性 .  且w(a, c) + w(b, d) <= w(b, c) + w(a, d)滿足四邊形不等式 .

AC代碼：

#include<cstdio>#include<algorithm>using namespace std;const int inf = 1 << 30;const int maxn = 1000 + 5;int dp[maxn][maxn], s[maxn][maxn], a[maxn], sum[maxn];//四邊形不等式優化 int solve(int n){	for(int i = 1; i <= n; ++i) {		dp[i][i] = 0;		s[i][i] = i;	}	for(int l = 2; l <= n; ++l) {		for(int i = 1; i <= n - l + 1; ++i) {			int j = i + l - 1;			dp[i][j] = inf;			int x = s[i][j-1], y = s[i+1][j];			for(int k = x; k <= y; ++k) {				int h = dp[i][k] + dp[k+1][j] + sum[j] - sum[i-1];				if(h < dp[i][j]) {					dp[i][j] = h;					s[i][j] = k;				}			}		}	}	return dp[1][n];}int main(){	int n;	while(scanf("%d", &n) == 1){		sum[0] = 0;		for(int i = 1; i <= n; ++i) {			scanf("%d", &a[i]);			sum[i] = sum[i - 1] + a[i];		}		PRintf("%d/n", solve(n));	}	return 0;}如有不當之處歡迎指出！