【CF713C】Sonya and Problem Wihtout a Legend（离散化，DP）

题意：给你一个数列，对于每个数字你都可以++或者−− 
然后花费就是你修改后和原数字的差值，然后问你修改成一个严格递增的，最小花费 

思路：很久以前做过一道一模一样的

        严格递增很难处理，就转化为非严格递增处理

        设a[i]<a[j],i<j

           a[j]-a[i]>=j-i 

           a[j]-j>=a[i]-i

        即将a[i]转化为a[i]-i处理

        非严格递增情况下最终数列一定是由原先的数组成的，不可能出现某两个原数中间的值

        dp[i,j]为第i位，结尾为第j大的数，转化成这样的数列的最小费用

        dp[i,j]=min(dp[i-1,k]+abs(a[i]-b[j])) k<=j

        第一项用前缀和优化

const oo=10000000000000;
var dp,f:array[0..3000,0..3000]of int64;
    a,b:array[1..3000]of longint;
    n,i,j:longint;
    ans:int64;

function min(x,y:int64):int64;
begin
 if x<y then exit(x);
 exit(y);
end;

procedure qsort(l,r:longint);
var i,j,t,mid:longint;
begin
 i:=l; j:=r; mid:=b[(l+r)>>1];
 repeat
  while mid>b[i] do inc(i);
  while mid<b[j] do dec(j);
  if i<=j then
  begin
   t:=b[i]; b[i]:=b[j]; b[j]:=t;
   inc(i); dec(j);
  end;
 until i>j;
 if l<j then qsort(l,j);
 if i<r then qsort(i,r);
end;

begin
 //assign(input,'1.in'); reset(input);
// assign(output,'1.out'); rewrite(output);
 readln(n);
 for i:=1 to n do
 begin
  read(a[i]);
  a[i]:=a[i]-i;
 end;
 b:=a;
 qsort(1,n);
 for i:=1 to n do
 begin
  for j:=0 to n do f[i,j]:=oo;
  for j:=1 to n do
  begin
   dp[i,j]:=abs(a[i]-b[j])+f[i-1,j];
   f[i,j]:=min(f[i,j-1],dp[i,j]);
  end;
 end;
 ans:=oo;
 for i:=1 to n do ans:=min(ans,dp[n,i]);
 writeln(ans);
 //close(input);
// close(output);
end.