1200: [HNOI2005]木梳 – BZOJ

Description

Input

第一行为整数L，其中4<=L<=100000，且有50%的数据满足L<=104，表示木板下侧直线段的长。第二行为L个正整数A1,A2,…,AL，其中1

Output

仅包含一个整数D，表示为使梳子面积最大，需要从木板上挖掉的格子数。

Sample Input

9

4 4 6 5 4 2 3 3 5

Sample Output

3

太坑爹了，证明在这里

最终方案中的a'[i]只可能是a[j]+k{|i-j|<=2,|k|<=1}

然后直接dp就行了

 var
     a:array[..]of longint;
     f:array[..,-..,-..,..]of int64;
     h:array[..,-..,-..]of longint;
     n:longint;
     ans:int64; function min(x,y:int64):int64;
 begin
     if x<y then exit(x);
     exit(y);
 end; procedure init;
 var
     i:longint;
 begin
     read(n);
     for i:= to n do
       read(a[i]);
     ans:=<<;
     fillchar(f,sizeof(f),);
 end; procedure work;
 var
     i,j,k,j1,k1:longint;
 begin
     for j:= to  do
       if +j<=n then
       for k:=- to  do
         if a[+j]+k<=a[] then
         begin
           h[,j,k]:=a[+j]+k;
           f[,j,k,]:=a[]-h[,j,k];
           f[,j,k,]:=a[]-h[,j,k];
         end;
     for i:= to n do
       for j:=- to  do
         if (i+j>)and(i+j<=n) then
         for k:=- to  do
           if a[i+j]+k<=a[i] then
           begin
             h[i,j,k]:=a[i+j]+k;
             for j1:=- to  do
               for k1:=- to  do
                 if h[i-,j1,k1]>h[i,j,k] then f[i,j,k,]:=min(f[i,j,k,],f[i-,j1,k1,]+a[i]-h[i,j,k])
                 else
                   if h[i-,j1,k1]<h[i,j,k] then f[i,j,k,]:=min(f[i,j,k,],f[i-,j1,k1,]+a[i]-h[i,j,k])
                   else
                     begin
                       f[i,j,k,]:=min(f[i,j,k,],f[i-,j1,k1,]+a[i]-h[i,j,k]);
                       f[i,j,k,]:=min(f[i,j,k,],f[i-,j1,k1,]+a[i]-h[i,j,k]);
                     end;
           end;
     for j:=- to  do
       for k:=- to  do
         ans:=min(ans,min(f[n,j,k,],f[n,j,k,]));
     write(ans);
 end; begin
     init;
     work;
 end.