終于把最后一道優化DP的題目做了，斜率優化之前掌握的不是非常熟練呀。
樸素方程：f[i]=min{f[k]+s[i]-s[k]-a[k+1]*(i-k)}。
就這么一個樸素方程的化簡，搞了很久。
把減號寫成加號導致化簡完全錯誤，糾結于直接用double還是用int64的x和y，后來有糾結于≤和≥的問題。這才完全搞定斜率優化。不錯的題目。
代碼：
var
q,f,s,a:array[0..500002] of int64;
head,tail,n,m,i,j,t:longint;
k,xx,yy,zz:int64;
function y(k,j:longint):int64;
begin
exit(f[k]-f[j]+s[j]-s[k]-a[j+1]*j+a[k+1]*k);
end;
function x(k,j:longint):int64;
begin
exit(a[k+1]-a[j+1]);
end;
begin
readln(t);
while t>0 do
begin
dec(t);
readln(n,m);
for i:=1 to n do
begin
read(a[i]);
s[i]:=s[i-1]+a[i];
end;
f[0]:=0;
head:=0;
tail:=0;
q[0]:=0;
for i:=1 to n do
begin
while (head<tail)and(y(q[head],q[head+1])>=i*x(q[head],q[head+1]))
do inc(head);
k:=q[head];
f[i]:=f[k]+s[i]-s[k]-a[k+1]*(i-k);
if i>=2*m-1 then
begin
zz:=i-m+1;
while head<tail do
begin
xx:=q[tail-1];
yy:=q[tail];
if y(xx,yy)*x(yy,zz)>=(y(yy,zz)*x(xx,yy)) then dec(tail)
else break;
end;
inc(tail);
q[tail]:=zz;
end;
end;
writeln(f[n]);
end;
end.
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
