【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=;

 var dp,f:array[..,..]of int64;

     a,b:array[..]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)>>];

  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:= to n do

  begin

   read(a[i]);

   a[i]:=a[i]-i;

  end;

  b:=a;

  qsort(,n);

  for i:= to n do

  begin

   for j:= to n do f[i,j]:=oo;

   for j:= to n do

   begin

    dp[i,j]:=abs(a[i]-b[j])+f[i-,j];

    f[i,j]:=min(f[i,j-],dp[i,j]);

   end;

  end;

  ans:=oo;

  for i:= to n do ans:=min(ans,dp[n,i]);

  writeln(ans);

  //close(input);

 // close(output);

 end.

巴特西

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

最新文章

热门文章