【tyvj1088】treat

2014年2月5日1,0600

题目描述

给出长度为N的数列{A_i},每次可以从最左边或者最右边取走一个数,第i次取数得到的价值是i  *  A_j。求价值之和最大的取数方案。

输入

第一行,一个整数,表示数列长度N。         接下来N行,每行一个整数,表示数列A_i。

输出

一个整数,表示最大的价值之和。

样例输入

5 1 3 1 5 2

样例输出

43

提示

N  < =  2000  ,  A_i  < =  1000

题解

dp或者记忆化搜索。。

f[i][j]表示左边取i个右边j个最大价值,方程比较好想。。

但是注意会有负数,所以都加上1