Tyvj p1088 广东汕头聿怀初中

描述 Description 

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

输入格式 Input Format 　　

第一行，一个整数，表示数列长度N。
接下来N行，每行一个整数，表示数列A_i。输出格式 Output Format 一个整数，表示最大的价值之和。样例输入 Sample Input 

5

1

3

1

5

2

样例输出 Sample Output               

时间限制 Time Limitation 各个测试点1s
注释 Hint 

N <= 2000 , A_i <= 1000

动态规划：

方程：  f[i,j]:=max(f[i-1,j-1]+i*a[j],f[i-1,j]+i*a[n-(i-j)+1]);

f[i,j]代表第i次取数，从前面取了j个的最大值

uses math;
var f:array[-1..2000,-1..2000] of longint;
    a:array[0..2000] of longint;
    n,i,j,k,max1:longint;
begin
 read(n);
  for i:=1 to n do
   read(a[i]);
 // f[1,1]:=a[1];
  for i:=0 to n do
   for j:=0 to i do
      f[i,j]:=max(f[i-1,j-1]+i*a[j],f[i-1,j]+i*a[n-(i-j)+1]);
    max1:=-maxlongint;
   for i:=1 to n do
     if f[n,i]>max1 then max1:=f[n,i];
   writeln(max1);
end.