P2858 [USACO06FEB]奶牛零食Treats for the Cows

约翰经常给产奶量高的奶牛发特殊津贴，于是很快奶牛们拥有了大笔不知该怎么花的钱．为此，约翰购置了N(1≤N≤2000)份美味的零食来卖给奶牛们．每天约翰售出一份零食．当然约翰希望这些零食全部售出后能得到最大的收益．这些零食有以下这些有趣的特性：

•零食按照1．．N编号，它们被排成一列放在一个很长的盒子里．盒子的两端都有开口，约翰每

天可以从盒子的任一端取出最外面的一个．

•与美酒与好吃的奶酪相似，这些零食储存得越久就越好吃．当然，这样约翰就可以把它们卖出更高的价钱．

•每份零食的初始价值不一定相同．约翰进货时，第i份零食的初始价值为Vi(1≤Vi≤1000)．

•第i份零食如果在被买进后的第a天出售，则它的售价是vi×a．

Vi的是从盒子顶端往下的第i份零食的初始价值．约翰告诉了你所有零食的初始价值，并希望你能帮他计算一下，在这些零食全被卖出后，他最多能得到多少钱．

输入格式 Line 1: A single integer, N

Lines 2…N+1: Line i+1 contains the value of treat v(i)

输出格式 Line 1: The maximum revenue FJ can achieve by selling the treats

输入输出样例输入 #1复制 5 1 3 1 5 2 输出 #1复制 43 说明/提示 Explanation of the sample:

Five treats. On the first day FJ can sell either treat #1 (value 1) or
treat #5 (value 2).

FJ sells the treats (values 1, 3, 1, 5, 2) in the following order of
indices: 1, 5, 2, 3, 4, making 1x1 + 2x2 + 3x3 + 4x1 + 5x5 = 43.

区间dp ，分析一下，我们每次要么从最前面拿，要么从最后面拿，然后中间一段是连续的，所以我们就可以用区间dp进行操作，按照惯例，
状态表示dp[i][j] ，表示区间i ， j的最大值，
初始状态：考虑每个i都有可能成为最后拿的dp[i][i] = a[i] * n
目标状态：求dp[1][n] , 表示整个区间最大值
那么我们要从最小的区间往最大的区间转移
第一步：枚举区间长度，可以在输入的时候就初始化一下长度为1的dp[i][i] , len从2到n
第二步：枚举起点， i = 1 ， i + len - 1 <= n ;i ++
第三步：状态转移：
因为我们当前区间dp[i][i + len - 1] ，这样考虑，因为我们要从当前区间拿出一个数，然后求最大值，此时，区间就可能变为两个dp[i + 1][i + len - 1] , 这个是从前端取， dp[i][i + len - 2] ，这个是从后端取，只需各自加上（a[i] 或 a[j] ）* （n - len + 1）, 转移方程就出来了

#include <iostream>
using namespace std;
int n ;
const int N = 2e4 + 10 ;
int a[N] , dp[2010][2010] ;
int main()
{
	cin >> n ;
	for(int i = 1 ;i <= n ;i ++)
	 cin >> a[i] , dp[i][i] = a[i] * n;
	for(int len = 2 ; len <= n ;len ++)
	 for(int i = 1 ;i + len - 1 <= n ;i ++)
	  dp[i][i + len - 1] = max(dp[i + 1][i + len - 1] + a[i] * (n - len + 1) , dp[i][i + len - 2] +a[i + len - 1] * (n - len + 1)) ;
	cout << dp[1][n] << endl ; 
	return 0 ;
}