博客

题目来源：

http://poj.org/problem?id=3666

题意：给定一个序列，可以对序列的任意一个数进行加减，使之序列成为一个不递增或者不递减的序列，改变数值1就花费价值1，问使之序列成为一个不递增或者不递减的序列最少需要多少价值。

思路：一开始看完题目，想对每个数进行分状态取递增或者递减，当到i时比较之前i-1的数值是多少，但是之前数值可取许多种不同的情况，i也有许多可取的数字情况，此方法不可行。但是发现依照不递增或者不递减情况，所有的数字变动都是依照之前的数字是多少由来，序列中的数字全部有联系，可知改变一个数值最好的情况就是变为1-n中数列的某一个数值。

之前的思路一定不行，不递增不递减前是都能化为一种情况，无非之后颠倒数列跑一边即可。所以我们可以先考虑不递减的情况。

dp[i][j]表示第i个数取值为j的时候让前i个数为不递减的序列的最小价值，列出转移方程：dp[i][j]=labs(a[i]-j)+min(dp[i-1][k])(0<=k<=j)（j的范围0-1e9）。而题中序列最大取值到1e9，必定超时。

考虑到之前得出的数值改变情况是变为1-n中第某个的数值，用b[]数组排列出即可，用b数组去代替j。

dp[i][j]=labs(a[i]-b[j])+min(dp[i-1][k])(1<=k<=j)但还是为O(n*n*n)

做一点点小的改动加入temp每次对比即可变为O(n*n)，最后逆向跑一遍比较正向哪个更小即可。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<vector>
#include<map>
#include<algorithm>
#include<queue>
#define MAX_len 50100*4
using namespace std;
typedef long long ll;
ll a[2010];
ll b[2010];
ll dp[2010][2010];
int main()
{
    int n,i,j;
    cin>>n;
    for(i=1;i<=n;i++)
    {
        cin>>a[i];
        b[i]=a[i];
    }
    sort(b+1,b+1+n);
    for(i=1;i<=n;i++)
    {
        ll hh=9999999999;
        for(j=1;j<=n;j++)
        {
            hh=min(dp[i-1][j],hh);
            dp[i][j]=labs(a[i]-b[j])+hh;
        }
    }
    ll ans=999999999;
    for(i=1;i<=n;i++)
        ans=min(ans,dp[n][i]);
    for(i=1;i<=n;i++)
    {
        ll tmp=a[i];
        a[i]=a[n-i+1];
        a[n-i+1]=tmp;
    }
    memset(dp,0,sizeof(dp));
        for(i=1;i<=n;i++)
    {
        ll hh=99999999999;
        for(j=1;j<=n;j++)
        {
            hh=min(dp[i-1][j],hh);
            dp[i][j]=labs(a[i]-b[j])+hh;
        }
    }
      for(i=1;i<=n;i++)
        ans=min(ans,dp[n][i]);
    printf("%lld",ans);
    return 0;
}