Pascal 取数描述 Description 给出长度为N的数列{A_i},每次可以从最左边或者最右边取走一个数,第i次取数得到的价值是i * A_j.求价值之和最大的取数方案.输入格式 Input Format 第一行,一个整数,表示
来源:学生作业帮助网 编辑:六六作业网 时间:2024/12/25 14:03:21
Pascal 取数描述 Description 给出长度为N的数列{A_i},每次可以从最左边或者最右边取走一个数,第i次取数得到的价值是i * A_j.求价值之和最大的取数方案.输入格式 Input Format 第一行,一个整数,表示
Pascal 取数
描述 Description
给出长度为N的数列{A_i},每次可以从最左边或者最右边取走一个数,第i次取数得到的价值是i * A_j.求价值之和最大的取数方案.
输入格式 Input Format
第一行,一个整数,表示数列长度N.
接下来N行,每行一个整数,表示数列A_i.
输出格式 Output Format
一个整数,表示最大的价值之和.
样例输入
5
1
3
1
5
2
样例输出
43
Pascal 取数描述 Description 给出长度为N的数列{A_i},每次可以从最左边或者最右边取走一个数,第i次取数得到的价值是i * A_j.求价值之和最大的取数方案.输入格式 Input Format 第一行,一个整数,表示
就是一个很简单的dp题.
var
n,m,i,j,k,t,s,d:longint;
a:array[0..2001] of longint;
f:array[-2..2001,-2..2001] of longint;
function max(p,q:longint):longint;
begin
if p>q then
exit(p)
else
exit(q);
end;
begin
readln(n);
for i:=1 to n do
readln(a[i]);
fillchar(f,sizeof(f),0);
for i:=1 to n do
for j:=n downto i-1 do
f[i,j]:=max(f[i,j+1]+(i-1+n-j)*a[j+1],f[i-1,j]+(i-j+n-1)*a[i-1]);
for i:=1 to n do
if s