1D1D动态规划，方程很容易写出来，
f[i]=min{f[j]+(i-(j+1)+s[i]-s[j]-l)^2} 红色的地方要注意，因为j已经装进去了，所以是从j+1到i。
通过函数性质，方程满足决策单调性，可以用二分法降到nlogn
注意要用int64
View Code
1 program hnoi2008_toy(input,output); 2 type 3 node = record 4 x,y,pos : longint; 5 end; 6 var 7 f : array[0..55000] of int64; 8 q : array[0..55000] of node; 9 n,l : longint; 10 c : array[-1..55000] of int64; 11 function calc(xx,yy: longint ):int64; 12 begin 13 calc:=sqr(xx-(yy+1)+(c[xx]-c[yy])-l)+f[yy]; 14 end; { calc } 15 procedure init; 16 var 17 i : longint; 18 begin 19 readln(n,l); 20 fillchar(c,sizeof(c),0); 21 for i:=1 to n do 22 begin 23 readln(c[i]); 24 inc(c[i],c[i-1]); 25 end; 26 end; { init } 27 procedure main; 28 var 29 head,tail : longint; 30 ll,rr,mid : longint; 31 i : longint; 32 begin 33 fillchar(f,sizeof(f),63); 34 f[0]:=0; 35 head:=1; 36 tail:=1; 37 q[1].x:=1; q[1].y:=n; q[1].pos:=0; 38 39 for i:=1 to n do 40 begin 41 f[i]:=calc(i,q[head].pos); 42 inc(q[head].x); 43 if q[head].x>q[head].y then 44 inc(head); 45 46 while (head<=tail)and(calc(q[tail].x,q[tail].pos)>calc(q[tail].x,i)) do 47 dec(tail); 48 if head>tail then 49 begin 50 inc(tail); 51 q[tail].x:=i+1; 52 q[tail].y:=n; 53 q[tail].pos:=i; 54 continue; 55 end; 56 57 ll:=q[tail].x; 58 rr:=q[tail].y+1; 59 while ll+1<rr do 60 begin 61 mid:=(ll+rr)>>1; 62 if calc(mid,i)<calc(mid,q[tail].pos) then 63 rr:=mid 64 else 65 ll:=mid; 66 end; 67 if rr=n+1 then 68 continue; 69 q[tail].y:=ll; 70 inc(tail); 71 q[tail].x:=rr; 72 q[tail].y:=n; 73 q[tail].pos:=i; 74 end; 75 writeln(f[n]); 76 end; { main } 77 begin 78 init; 79 main; 80 end.
最近学了斜率优化，O(n)算法放在这里了
View Code
1 program toys(input,output); 2 var 3 q :array[0..60000] of longint; 4 f,g,s,w :array[0..60000] of int64; 5 n,l :longint; 6 procedure init; 7 var 8 i:longint; 9 begin 10 readln(n,l); 11 for i:=1 to n do 12 begin 13 readln(s[i]); 14 s[i]:=s[i]+s[i-1]+1; 15 end; 16 end;{ init } 17 function K(x,y:longint):double; 18 begin 19 exit(double(g[x]-g[y])/double(w[x]-w[y])); 20 end;{ K } 21 procedure main; 22 var 23 i :longint; 24 head,tail:longint; 25 bestk :double; 26 begin 27 head:=1; 28 tail:=1; 29 q[1]:=0; 30 f[0]:=0; 31 for i:=1 to n do 32 begin 33 bestk:=double(s[i]); 34 while (tail>head)and(K(q[head],q[head+1])<=bestk) do 35 inc(head); 36 f[i]:=int64(f[q[head]])+int64(s[i]-s[q[head]]-l-1)*int64(s[i]-s[q[head]]-l-1); 37 w[i]:=2*s[i]; 38 g[i]:=f[i]+2*(l+1)*s[i]+s[i]*s[i]; 39 while (tail>head)and(K(q[tail-1],q[tail])>K(q[tail],i)) do 40 dec(tail); 41 inc(tail); 42 q[tail]:=i; 43 end; 44 end;{ main } 45 procedure print; 46 begin 47 writeln(f[n]); 48 end;{ print } 49 begin 50 init; 51 main; 52 print; 53 end.