单调队列DP复出练手题
朴素方程dp[i]=min(dp[j]+(s[i]-s[j-1])^2+m
你懂得
1 var dp,s:array[0..500000]of int64; 2 a,q:array[1..500000]of longint; 3 n,m,i,t,w:longint; 4 5 function sum(x,y:longint):int64; 6 begin 7 exit(s[y]-s[x-1]); 8 end; 9 10 function clac(j,i:longint):int64; 11 begin 12 exit(dp[j]+sqr(sum(j+1,i))+m); 13 end; 14 15 function cmp(x,y,z:longint):boolean; 16 var x1,y1,x2,y2:int64; 17 begin 18 x1:=dp[x]-dp[y]+sqr(s[x])-sqr(s[y]); 19 y1:=2*(s[x]-s[y]); 20 x2:=dp[y]-dp[z]+sqr(s[y])-sqr(s[z]); 21 y2:=2*(s[y]-s[z]); 22 if x1*y2>=x2*y1 then exit(true); 23 exit(false); 24 end; 25 26 begin 27 assign(input,'1.in'); reset(input); 28 assign(output,'1.out'); rewrite(output); 29 while not eof do 30 begin 31 readln(n,m); 32 fillchar(dp,sizeof(dp),0); 33 for i:=1 to n do readln(a[i]); 34 s[0]:=0; 35 for i:=1 to n do s[i]:=s[i-1]+a[i]; 36 t:=1; w:=1; q[1]:=0; dp[0]:=0; 37 for i:=1 to n do 38 begin 39 while (w-t>=1)and(clac(q[t],i)>=clac(q[t+1],i)) do inc(t); 40 dp[i]:=clac(q[t],i); 41 while (w-t>=1)and cmp(q[w-1],q[w],i) do dec(w); 42 inc(w); q[w]:=i; 43 end; 44 writeln(dp[n]); 45 end; 46 close(input); 47 close(output); 48 end.