网站页面
当前课程
成员
General
主题 1
主题 2
主题 4
主题 5
主题 6
主题 7
主题 8
主题 9
主题 10
主题 11
主题 12
主题 13
主题 14
主题 15
主题 16
主题 17
主题 18
主题 19
主题 20
删数
成绩 | 0 | 开启时间 | 2013年02月21日 星期四 23:02 |
折扣 | 0.8 | 折扣时间 | 2013年02月28日 星期四 23:02 |
允许迟交 | 是 | 关闭时间 | 2013年02月28日 星期四 23:02 |
输入文件 | remove.in | 输出文件 | remove.out |
【问题描述】
有 N 个不同的正整数数 x 1 , x 2 , ... x N 排成一排,我们可以从左边或右边去掉连续的 i 个数(只能从两边删除数), 1<=i<=n ,剩下 N-i 个数,再把剩下的数按以上操作处理,直到所有的数都被删除为止。
每次操作都有一个操作价值,比如现在要删除从 i 位置到 k 位置上的所有的数。操作价值为 |x i – x k |*(k-i+1) ,如果只去掉一个数,操作价值为这个数的值。
任务
如何操作可以得到最大值,求操作的最大价值。
Input Data
输入文件 remove.in 的第一行为一个正整数 N ,第二行有 N 个用空格隔开的 N 个不同的正整数。
Output Data
输出文件 remove.out 包含一个正整数,为操作的最大值
约束和提示
3<=N<=100
N 个操作数为 1..1000 之间的整数。
样例
remove.in
6
54 29 196 21 133 118
remove.out
768
说明:经过 3 次操作可以得到最大值,第一次去掉前面 3 个数 54 、 29 、 196 ,操作价值为 426 。第二次操作是在剩下的三个数( 21 133 118 )中去掉最后一个数 118 ,操作价值为 118 。第三次操作去掉剩下的 2 个数 21 和 133 ,操作价值为 224 。操作总价值为 426+118+224=768 。