删数

P1078 删数

时间: 1000ms / 空间: 131072KiB / Java类名: Main

描述

有N个不同的正整数数x1, x2, ... xN 排成一排，我们可以从左边或右边去掉连续的i个数（只能从两边删除数），1<=i<=n，剩下N-i个数，再把剩下的数按以上操作处理，直到所有的数都被删除为止。
每次操作都有一个操作价值，比如现在要删除从i位置到k位置上的所有的数。操作价值为|xi – xk|*(k-i+1)，如果只去掉一个数，操作价值为这个数的值。
任务
如何操作可以得到最大值，求操作的最大价值。 

输入格式

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

输出格式

输出文件remove.out 包含一个正整数，为操作的最大值

测试样例1

输入

6 
54 29 196 21 133 118

输出

768

 

---

本来用记忆化搜索写了一个结果交了以后发现自己的程序在排名当中是最慢的一个于是打算优化一下QAQ

记忆化搜索思路：先开个函数处理一下删数的操作价值，当只删一个数的时候它的价值就是它本身，其他的时候操作价值为|xi – xk|*(k-i+1)，由此得到了第一个函数

第二段记忆化搜索，分两边依次判断左右两段哪边删数的操作价值比较资磁题意，得到状态转移方程

f[l][r]=max(f[l][r],dp(l,i)+ds(i+1,r));
f[l][r]=max(f[l][r],dp(i+1,r)+ds(l,i));

然后就得出了一个奇慢无比的记忆化搜索QAQ

#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
int a[2005],n;
int f[2000][2000];
int ds(int x, int y) 
{
    if (x == y) return a[x];
    return abs(a[x]-a[y])*(y-x+1);
}
int dp(int l,int r)
{
    if(f[l][r]!=-1)return f[l][r];
    f[l][r]=ds(l,r);
    for(int i=l;i<r;i++)
    {
        f[l][r]=max(f[l][r],dp(l,i)+ds(i+1,r));
        f[l][r]=max(f[l][r],dp(i+1,r)+ds(l,i));
    }
    return f[l][r];
}
int main() 
{ 
    cin>>n; 
    memset(f,-1,sizeof(f));
    for(int i=1;i<=n;i++) 
    { 
        scanf("%d",&a[i]);
    } 
    
    cout<<dp(1,n);
    puts("");
    return 0;
}

---