【Tyvj1078】删数

2014-05-22
竞赛题解 / 动态规划
TYVJ

描述 Description

有 N 个不同的正整数数 x1, x2, … xN 排成一排，我们可以从左边或右边去掉连续的 i 个数（只能从两边删除数），1<=i<=n，剩下 N-i 个数，再把剩下的数按以上操作处理，直到所有的数都被删除为止。

每次操作都有一个操作价值，比如现在要删除从 i 位置到 k 位置上的所有的数。操作价值为 | xi – xk|*(k-i+1)，如果只去掉一个数，操作价值为这个数的值。 任务

如何操作可以得到最大值，求操作的最大价值。

输入格式 InputFormat

第一行为一个正整数 N，第二行有 N 个用空格隔开的 N 个不同的正整数。
3<=N<=100,N 个操作数为 1..1000 之间的整数。

输出格式 OutputFormat

包含一个正整数，为操作的最大值

样例输入 SampleInput

40
11 139 177 146 141 124 121 58 120 73 92 15 184 41 53 166 158 75 27 159 122 109 112 74 200 116 171 8 114 13 55 81 194 47 102 165 56 130 9 95

样例输出 SampleOutput

7042

Tyvj 1078

代码 Code

第一眼区间动规，但其实从左边开始做就行了。于是变成了线性动规。

#include <stdio.h>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
int f[101];
int a[101];
int i,j,t,n,m,l,r,k,z,y,x;
int main()
{
    scanf("%d",&n);
    for (i=1;i<=n;i++) scanf("%d",&a[i]);
    f[1]=a[1];
    for (i=2;i<=n;i++) 
    {
        f[i]=max(f[i],f[i-1]+a[i]);
        for (j=1;j<i;j++)
        {
            f[i]=max(f[i],f[j-1]+abs(a[i]-a[j])*(i-j+1));
        }
    }
    printf("%d\n",f[n]);
    return 0;
}