BZOJ3594 SCOI2014 Maize

好像我在考场上A了这道题www才进队的

题意

  给定长度N的序列A,准许你进行M次把某个区间[L,R]中的元素值全部加一的操作

  最大化这M次之后A的单调不降子序列长度

  N!>10000;M!>500;ai in [1..5000]

Tag DP BIT/ZKW线段树

易证每次一定是操作区间[i,N],设操作从左到右,那么操作完i,i之后的相对高度差不变

考完Day1我所遇到的人除了写[神奇贪心]的神,都写出了以下的DP方程(然后神跪了)

        f[i,j]=max{f[k,j-cost(k,i)]+1}

f[i,j] 1..i操作j次最长不降子序列长度,最长不降子序列一定包含i

cost(k,i) max{0,h[k]-h[i]}

不过这只有10分(泣)

因为ai in [1..5000] 不妨从ai的角度思考

定义 g[i,j] 至今为止初始高度为i,使用j次魔法操作j次的最长非下降子序列长度,显然重写方程

        f[i,j]=max{g[k,j-max{0,k-h[i]}]+1}

算完f[i,j]之后再更新g就可以了

我们思考每次查询g的位置的规律,容易得到(1:查询;空格:不查询)

{            j    

             1    

             1    

             1    

            1     

           1      

          1       

         1        

}

每次都是查询某列的前h[i]个和某对角线的前若干个的最小值

显然这里就是BIT的用场了(考场上我写的ZKW线段树因为当时不会BIT)

每次查询前若干个的RMQ,BIT是很容易搞的.更新再搞搞也可以了

时间 O(knlgU),常数较大好像我在考场上A了这道题www才进队的

program bzoj3594;
  
const maxn=10017;
      maxm=517;
      maxu=5017;
      maxint=longint($3f3f3f3f);
      minint=longint($c0c0c0c0);
  
var f:array[0..maxn,0..maxm] of longint;
    g1:array[0..maxm,0..maxu] of longint;
    g2:array[0..6017,0..maxm+17] of longint;
    h:array[0..maxn] of longint;
    n,m,maxh:longint;
  
function max(i,j:longint):longint; begin
if i>j then exit(i) else exit(j);  end;
  
function lowbit(n:longint):longint;
inline; begin exit(n and(-n)); end;
  
function premax1(slot,i:longint):longint;
begin
premax1:=minint; while i>0 do begin
        premax1:=max(premax1,g1[slot][i]);
        dec(i,lowbit(i));
end;
end;
  
function premax2(slot,i:longint):longint;
begin
premax2:=minint; while i>0 do begin
        premax2:=max(premax2,g2[slot][i]);
        dec(i,lowbit(i));
end;
end;
  
procedure edit1(slot,i,j:longint);
begin
while i<=maxh do begin
        g1[slot][i]:=max(g1[slot][i],j);
        inc(i,lowbit(i));
end;
end;
  
procedure edit2(slot,i,j:longint);
var len:longint;
begin
if slot<=m then len:=slot
else if slot<=maxh then len:=m+1
else len:=m+1-slot+maxh;
while i<=len do begin
        g2[slot][i]:=max(g2[slot][i],j);
        inc(i,lowbit(i));
end;
end;
  
procedure init;
var i:longint;
begin
fillchar(f,sizeof(f),0); fillchar(g1,sizeof(g1),0);
readln(n,m); for i:=1 to n do begin
        read(h[i]); maxh:=max(maxh,h[i]);
end; readln;
end;
  
function dp:longint;
var i,j,k,t,slot,pos:longint;
begin
dp:=0; for i:=1 to n do
        for j:=0 to m do begin
  
                t:=premax1(j,h[i]);
                f[i,j]:=t+1;
  
                slot:=h[i]+j;
                if slot<maxh then
                        pos:=j+1
                else    pos:=j+1-slot+maxh;
                t:=premax2(slot,pos);
                f[i,j]:=max(f[i,j],t+1);
  
                dp:=max(dp,f[i,j]);
                edit1(j, h[i],f[i,j]);
                edit2(slot,  pos,f[i,j]);
        end;
end;
  
begin
init;
writeln(dp);
end.