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[];
int a[],p[],n;
int read(){
int t=,f=;char ch=getchar();
while (ch<''||ch>''){if (ch=='-') f=-;ch=getchar();}
while (''<=ch&&ch<=''){t=t*+ch-'';ch=getchar();}
return t*f;
}
int main(){
n=read();for (int i=;i<=n;i++) a[i]=read(),p[i]=a[i];
std::sort(p+,p++n);int j=;
for (int i=;i<=n;i++) if (p[i]!=p[i-]) p[++j]=p[i];
p[]=j;
for (int i=;i<=n;i++){
for (j=;j<=p[];j++){
if (j==) f[j]+=std::abs(a[i]-p[j]);
else f[j]=std::min(f[j-],f[j]+std::abs(a[i]-p[j]));
}
}
printf("%I64d\n",f[p[]]);
}