更好的阅读体验：https://www.cnblogs.com/To-Carpe-Diem/p/19527051

大意

石子合并，$n = 1000$，求最小值。

思路

首先 $\mathcal{O}(n ^ 3)$ 的复杂度肯定是不可以的。

我们考虑优化，不难发现，对于 $w(i, j)$ 满足：

$$w(i, j - 1) + w(i + 1, j) \le w(i, j) + w(i - 1,j - 1)$$

所以这个 $w$ 满足四边形不等式，故 $f$ 也满足。

然后我们定义这个 $G(k) = f(i, k) + f(k + 1, j)$，所以 $G(k)$ 为凹函数，则最小值在一个区间内取得，我们可以记录 $[i, j]$ 区间的决策点，这样你在算第 $[i, j]$ 的时候，区间 DP 的点 $k$ 就可以在 $s[i][j - 1]$ 和 $s[i + 1][j]$ 之间取得。

代码

#include<iostream>
using namespace std;

#define int long long
const int MAXN = 2005;
int n;
int a[MAXN];
int dp[MAXN][MAXN];
int sum[MAXN];
int s[MAXN][MAXN];

signed main(){

	cin >> n;

	for(int i = 1;i <= n;i ++){
		cin >> a[i];
		a[i + n] = a[i];
		sum[i] = sum[i - 1] + a[i];
	}

	for(int i = n + 1;i <= (n << 1);i ++){
		sum[i] = sum[i - 1] + a[i];
	}

	for(int i = 1;i <= (n << 1);i ++){
		s[i][i] = i;
	}

	for(int len = 2;len <= n;len ++){
		for(int i = 1;i + len - 1 <= (n << 1);i ++){
			int j = i + len - 1;
			dp[i][j] = 1e9;
			int L = s[i][j - 1];
			int R = s[i + 1][j];
			for(int k = L;k <= R;k ++){
				int cnt = dp[i][k] + dp[k + 1][j] + sum[j] - sum[i - 1];
				if(cnt < dp[i][j]){
					dp[i][j] = cnt;
					s[i][j] = k;
				}
			}
		}
	}

	int ans = 1e9;

	for(int i = 1;i <= n;i ++){
		ans = min(ans, dp[i][i + n - 1]);
	}

	cout << ans << '\n';
	return 0;
}