1049: [HAOI2006]数字序列

Description

现在我们有一个长度为n的整数序列A。但是它太不好看了，于是我们希望把它变成一个单调严格上升的序列。但是不希望改变过多的数，也不希望改变的幅度太大。
Input

第一行包含一个数n，接下来n个整数按顺序描述每一项的键值。
Output

第一行一个整数表示最少需要改变多少个数。第二行一个整数，表示在改变的数最少的情况下，每个数改变的绝对值之和的最小值。
Sample Input
4
5 2 3 5
Sample Output
1
4

【数据范围】
90%的数据n<=6000。
100%的数据n<=35000。
保证所有数列是随机的。

这个算法的复杂度真的是O（n^2）吗？怎么我觉得不对呢

和机房的小伙伴讨论之后，觉得这个复杂度应该是O（n^3）的（虽然跑得很快）

先转换一下，b[i]=a[i]-i，然后就是求b的最长不下降了，这样好算代价一些

cost[i]=cost[j]+w(j,i)(f[j]=f[i]-1,j<i)

计算w的时候有一个定理，肯定有一种最优方案是把左半边变成b[j]右半边变成b[i]

证明：http://pan.baidu.com/share/link?uk=2651016602&shareid=1490516411

 const

     maxn=;

     inf=;

 var

     a,f,b,first,next,last:array[..maxn]of longint;

     g:array[..maxn]of int64;

     n,tot,max:longint;

 procedure insert(x,y:longint);

 begin

     inc(tot);

     last[tot]:=y;

     next[tot]:=first[x];

     first[x]:=tot;

 end;

 procedure find(x:longint);

 var

     l,r,mid:longint;

 begin

     l:=;

     r:=n;

     while l<>r do

       begin

         mid:=(l+r)>>;

         if b[mid]>a[x] then r:=mid

         else l:=mid+;

       end;

     if max<l then max:=l;

     f[x]:=l;

     b[l]:=a[x];

     insert(l,x);

 end;

 procedure init;

 var

     i:longint;

 begin

     read(n);

     for i:= to n do

       begin

         read(a[i]);

         dec(a[i],i);

       end;

     inc(n);

     a[n]:=inf-;

     a[]:=-inf;

     for i:= to n do

       b[i]:=inf;

     insert(,);

 end;

 function calc(l,r:longint):int64;

 var

     i:longint;

     s:int64;

 begin

     s:=;

     for i:=l to r do

       inc(s,abs(a[i]-a[r]));

     calc:=s;

     for i:=l to r do

       begin

         s:=s-abs(a[i]-a[r])+abs(a[i]-a[l]);

         if calc>s then calc:=s;

       end;

 end;

 procedure work;

 var

     i,j:longint;

     num:int64;

 begin

     for i:= to n do

       begin

         find(i);

         g[i]:=inf*inf;

         j:=first[f[i]-];

         while j<> do

           begin

             if a[last[j]]<=a[i] then

               begin

                 num:=calc(last[j],i);

                 if g[i]>g[last[j]]+num then g[i]:=g[last[j]]+num;

               end;

             j:=next[j];

           end;

       end;

     writeln(n-max);

     write(g[n]);

 end;

 begin

     init;

     work;

 end.

pascal第三（前两名是怎么回事......）

巴特西

1049: [HAOI2006]数字序列 - BZOJ

最新文章

热门文章