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.