B 跳跳跳

题目大意：

给出n个点组成的环，每个点有一个权值为a[i],每次可以跳到一个未进过的点p,贡献为a[p] * i,问安排一种顺序使得贡献最大。

思路：

不管我们怎么跳，跳过的点都可以看成是一个区间，那我们每次跳跃就可以成是向区间左/右边扩大一格。

设f[i][j]表示区间[i,j]的最大贡献 那根据我们上面所说的，转移方程就是：

$f[i][j]=max(f[i][j],max(f[i+1][j]+a[i]\ast len,f[i][j-1]+a[j]\ast len);f[i][j]\; =\; max(f[i][j],\; max(f[i\; +\; 1][j]\; +\; a[i]\; *\; len,\; f[i][j-1]\; +\; a[j]\; *\; len);$

#include <cstdio>
#include <iostream>

using namespace std;

const int N = 2e3 + 10;
int n, a[N * 2], f[N * 2][N * 2], ans;

int main()
{
	scanf("%d", &n);
	for(int i = 1; i <= n; i++)
	{
		scanf("%d", &a[i]);
		a[i + n] = a[i];
		f[i][i] = f[i + n][i + n] = a[i];
	}
	for(int len = 2; len <= n; len++)
	{
		for(int i = 1; i + len - 1 <= 2 * n; i++)
		{
			int j = i + len - 1;
			f[i][j] = max(f[i][j], max(f[i + 1][j] + a[i] * len, f[i][j - 1] + a[j] * len));
		}	
	} 
	for(int i = 1; i <= n; i++) ans = max(ans, f[i][i + n - 1]);
	printf("%d\n", ans);
	return 0;
}