区间动规输出 99 求调

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 2 * 1e3 + 5;
int n, ans, a[maxn], dp[maxn][maxn];
signed main()
{
    cin >> n;
    for (int i = 1; i <= n; ++ i)
    {
    	cin >> a[i];
    	if (i != n)
    	{
    		a[i + n] = a[i];
		}
	}
	memset(dp, -1, sizeof dp);
	for (int i = 0; i < maxn; ++ i)
	{
		dp[i][i] = 0;
	}
	for (int len = 2; len <= n; ++ len)
	{
		for (int i = 1; i + len < 2 * n; ++ i)
		{
			int l = i, r = i + l - 1;
			for (int j = l; j < r; ++ j)
			{
				int h = r + 1;
				if (h > n)
				{
					h = 1;
				}
				dp[l][r] = max(dp[l][r], dp[l][j] + dp[j + 1][r] + a[l] * a[j + 1] * a[h]);
			}
		}
	}
	for (int i = 1; i + n - 1 <= 2 * n; ++ i)
	{
		ans = max(ans, dp[i][i + n - 1]);
	}
	cout << ans;
	return 0;
}