每日AC（有时会断）

#include <iostream>
#include <vector>
#include <climits>
#include <algorithm>
using namespace std;

int main() {
	int n;
	cin >> n;
	vector<int> a(n);
	for (int i = 0; i < n; ++i) {
    	cin >> a[i];
	}
	vector<int> s(2 * n);
	for (int i = 0; i < 2 * n; ++i) {
    	s[i] = a[i % n];
	}
	vector<int> sum(2 * n + 1, 0);
	for (int i = 1; i <= 2 * n; ++i) {
    	sum[i] = sum[i - 1] + s[i - 1];
	}
	vector<vector<int>> dp(2 * n, vector<int>(2 * n, INT_MAX));
	for (int i = 0; i < 2 * n; ++i) {
    	dp[i][i] = 0;
	}
	for (int len = 2; len <= 2 * n; ++len) {
    	for (int i = 0; i + len <= 2 * n; ++i) {
        	int j = i + len - 1;
        	for (int k = i; k < j; ++k) {
            	if (dp[i][k] != INT_MAX && dp[k+1][j] != INT_MAX) {
                	int cost = dp[i][k] + dp[k+1][j] + (sum[j+1] - sum[i]);
                	dp[i][j] = min(dp[i][j], cost);
            	}
        	}
    	}
	}
	int min_cost = INT_MAX;
	for (int i = 0; i < n; ++i) {
    	int j = i + n - 1;
    	min_cost = min(min_cost, dp[i][j]);
	}

	cout << min_cost << endl;

	return 0;
}