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

大意

$n = 2000$ 的石子合并。

思路

首先，区间 DP 是 $\mathcal{O}(n ^ 3)$ 的，对于这个题显然是不合适的。

我们考虑优化。

令 $G(k) = f(i, k) + f(k + 1, j)$。

我们接下来证明这个 $G(k)$ 为凸函数，则 $G(k) \le \displaystyle\frac{G(k - 1) + G(k + 1)}{2}$

令 $\Delta G(k) = G(k + 1) - G(k)$

$\Delta G(k) = [f(i, k + 1) - f(i, k)] - [f(k + 1, j) - f(k + 2, j)]$

左边的 $f(i, k + 1) - f(i, k)$ 随着 $k$ 的增大递增。

右边的 $f(k + 1, k) - f(k + 2, j)$ 随着 $k$ 的增大递减。

递增 - 递减 = 递增。

故 $G(k)$ 单调递增，则 $G(k)$ 为凸函数，最大值在端点处取得。

所以最终的转移式为：

$$f(i, j) = \max(f(i+1, j), f(i, j-1)) + w(i, j)$$

代码

#include<iostream>
using namespace std;

#define int long long
const int MAXN = 4 * 1e3 + 5;
int n;
int a[MAXN];
int dp[MAXN][MAXN];
int sum[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 len = 2;len <= n;len ++){
		for(int i = 1;i + len - 1 <= (n << 1);i ++){
			int j = i + len - 1;
			dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]) + (sum[j] - sum[i - 1]);
		}
	}
	
	int ans = -1;
	
	for(int i = 1;i <= n;i ++){
		ans = max(ans, dp[i][i + n - 1]);
	}
	
	cout << ans << '\n';
	return 0;
}