记录编号	611093	评测结果	AAAAA
题目名称	石子合并I	最终得分	100
用户昵称	终焉折枝	是否通过	通过
代码语言	C++	运行时间	0.148 s
提交时间	2026-01-24 15:33:24	内存使用	21.47 MiB

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