记录编号	611184	评测结果	AAAAAAAAAA
题目名称	石子合并II	最终得分	100
用户昵称	终焉折枝	是否通过	通过
代码语言	C++	运行时间	0.842 s
提交时间	2026-01-24 16:51:41	内存使用	42.18 MiB

#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;
}