一道不错的dp题
就是最小修改代价，使序列变为一个非下降序或非上升（由于数据较弱直接求非下降即可，当然非上升非下降本质是一样的）
观察可得到，修改后得到的数列中的元素最后一定都在原序列中；
由此我们可以将原数列排序离散化；
在dp[i,j]表示新序列到第i个元素修改成原序列第j小的数所用的代价
易得dp[i,j]=min(dp[i-1,k])+abs(p[i]-a[j]) (1<=k<=j)； a是原数列，p是排序后的
由于n<=1000 看起来这样的方程式O(n^3)会超时；
实际上，我们在处理的时候，完全可以优化成O(n^2);
由于abs(p[i]-a[j])是一个定值，不受k影响，所以我们可以先用dp[i,j]表示min(dp[i-1,k]) (1<=k<=j)
则dp[i,j+1]=min(d[i,j],d[i-1,j]);
最后再集体加上abs(p[i]-a[j])即可实现O(n^2)
var f:array[..,..] of longint;
a,p:array[..] of longint;
n,i,k1,k2,j,ans:longint; procedure swap(var a,b:longint);
var c:longint;
begin
c:=a;
a:=b;
b:=c;
end; function min(a,b:longint):longint;
begin
if a>b then exit(b) else exit(a);
end; procedure sort(l,r: longint);
var i,j,x: longint;
begin
i:=l;
j:=r;
x:=a[(l+r) div ];
repeat
while a[i]<x do inc(i);
while x<a[j] do dec(j);
if not(i>j) then
begin
swap(a[i],a[j]);
inc(i);
j:=j-;
end;
until i>j;
if l<j then sort(l,j);
if i<r then sort(i,r);
end; begin
readln(n);
for i:= to n do
begin
readln(a[i]);
p[i]:=a[i];
end;
sort(,n);
k1:=;
k2:=;
for i:= to n do
begin
k1:=k1 xor ;
k2:=k2 xor ;
f[k2,]:=f[k1,];
for j:= to n do
f[k2,j]:=min(f[k2,j-],f[k1,j]);
for j:= to n do
f[k2,j]:=f[k2,j]+abs(p[i]-a[j]);
end;
ans:=;
for i:= to n do
ans:=min(f[k2,i],ans);
writeln(ans);
end.