Codeforces 13C Sequence

http://codeforces.com/contest/13/problem/C

題目大意

給定一個含有N個數的序列，要求你對一些數減掉或者加上某個值，使得序列變為非遞減的，問你加減的值的總和最少是多少？

思路:所有數最終構成的集合一定是一開始所有數構成數的集合的子集，是以dp[i][j]代表目前第i個數，遞增序列在第j個數的代價。

#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
#define ll long long
ll f[5005];
int a[5005],p[5005],n;
int read(){
    int t=0,f=1;char ch=getchar();
    while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
    while ('0'<=ch&&ch<='9'){t=t*10+ch-'0';ch=getchar();}
    return t*f;
}
int main(){
    n=read();for (int i=1;i<=n;i++) a[i]=read(),p[i]=a[i];
    std::sort(p+1,p+1+n);int j=1;
    for (int i=2;i<=n;i++) if (p[i]!=p[i-1]) p[++j]=p[i];
    p[0]=j;
    for (int i=1;i<=n;i++){
      for (j=1;j<=p[0];j++){
        if (j==1) f[j]+=std::abs(a[i]-p[j]);
        else f[j]=std::min(f[j-1],f[j]+std::abs(a[i]-p[j]));
        }
    }
    printf("%I64d
",f[p[0]]);
}