[BZOJ3437] 小P的牧场

本文主要是介绍[BZOJ3437] 小P的牧场，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

传送门

http://www.lydsy.com/JudgeOnline/problem.php?id=3437

题目大意

。。。

题解

斜率优化

uses math;
constmaxn=1000000;
varsum1,sum2,s,x,f:array[0..maxn]of int64;t:array[0..maxn]of longint;i,j,k:longint;n,m,a,head,tail:longint;tt:int64;
function check1(a,b,c:longint):boolean;
beginexit((s[a]-s[b])>int64(c)*(sum1[a]-sum1[b]));
end;function check2(a,b,c:longint):boolean;
beginexit(((s[a]-s[b])*(sum1[b]-sum1[c]))>((s[b]-s[c])*(sum1[a]-sum1[b])));
end;beginreadln(n); sum1[0]:=0; sum2[0]:=0;for i:=1 to n doread(x[i]);for i:=1 to n dobeginread(a);sum1[i]:=sum1[i-1]+a;sum2[i]:=sum2[i-1]+int64(a)*i;end;head:=0; tail:=0; f[0]:=0;for i:=1 to n dobeginwhile (head<tail)and(check1(t[head],t[head+1],i)) do inc(head);f[i]:=f[t[head]]+x[i]+(sum1[i-1]-sum1[t[head]])*i-(sum2[i-1]-sum2[t[head]]);s[i]:=f[i]+sum2[i];while (head<tail)and(check2(t[tail-1],t[tail],i)) do dec(tail);inc(tail); t[tail]:=i;end;writeln(f[n]);
end.

这篇关于[BZOJ3437] 小P的牧场的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---