Note: 本文最初于 2011年01月22日 星期六 21:21 在 hi.baidu.com/lydrainbowcat 发表。
分析：
设s[i]表示前i个士兵的战斗力和。
原方程很容易想到:f[i] = max{f[k]+A(s[i]-s[k])^2+B(s[i]-s[k])+C} 时间复杂度O(n^2)
下面我们可以考虑使用四边形不等式(单调决策)或者斜率优化本题。
假设j，k为两个断点，j<k，j比k更优，则有：
f[j]+A(s[i]-s[j])^2+B(s[i]-s[j])+C >= f[k]+A(s[i]-s[k])^2+B(s[i]-s[k])+C
把上式展开、移项：
f[j]-f[k] + A(s[j]^2-s[k]^2-2*s[i]*s[j]+2*s[i]*s[k]) + B(s[k]-s[j])>=0
继续展开：
f[j]+A*s[j]^2-2A*s[i]*s[j]-B*s[j] >= f[k]+A*s[k]^2-2A*s[i]*s[k]-B*s[k]
设关于j的一次函数G(j)=f[j]+A*s[j]^2-B*s[j] ，H(j)=-2*A*s[j]，对于k同理
则上式变为：
s[i]*H(j)+G(j)>=s[i]*H(k)+G(k)
首先它是是一个关于s[i]的一次函数。继续移项,并注意到H(j)<H(k)：
[G(j)-G(k)]/[H(j)-H(k)]<=s[i] && j比k优
随着i的增加，我们每次可以放入一个断点，那么若把j和k看做放入一个队列中，相邻两项比值就是递增的，所以我们用一个相邻两项比值递增的单调队列来维护最优决策点。
注意，我们队列中从前到后插入的时间也是递增的，随着循环i的增加，比值即s[i]也不断增加，就有：
相邻两项比值递增>> [G(k1)-G(k2)]/[H(k1)-H(k2)]<=[G(k2)-G(k3)]/[H(k2)-H(k3)]<=…… >> k1比k2比k3优
所以：队首最优。又由于i的增加，有可能某一时刻队首两个元素比值不再满足<=s[i]，此时需要删除某些队首元素。同时每次将最新的i插入到合适位置。
具体操作见代码：
var n,a,b,c,l,r,x,i:longint; q:array[0..2000000]of longint; f,g,h,sum:array[0..1000000]of int64; begin //assign(input,'commando.in');reset(input); //assign(output,'commando.out');rewrite(output); readln(n); readln(a,b,c); for i:=1 to n do begin read(x); sum[i]:=sum[i-1]+x; h[i]:=2*a*sum[i]; end; l:=1; r:=2; q[1]:=0; q[2]:=1; f[0]:=0; f[1]:=a*sqr(sum[1])+b*sum[1]+c; //注意：我们维护的是f数组下标下标递增，而且相邻两项斜率递增的队列。 for i:=2 to n do begin //注意f[]和sun[]中括号里是q[l]或q[r]，别丢了q，我起初不仔细，丢掉了q，结果纠结了1个小时就是不知道哪错了！！！ while (l<r)and(f[q[l]]-f[q[l+1]]+a*(sqr(sum[q[l]])-sqr(sum[q[l+1]]))+b*(sum[q[l+1]]-sum[q[l]])<=h[i]*(sum[q[l]]-sum[q[l+1]])) do inc(l); //由于在每次i循环加一以后，h[i]=2*a*sum[i]必然会增大，这就可能会使得队首的某些相邻元素之间的斜率已经不满足更优的条件，这时就要队首后移直到满足为止。 f[i]:=f[q[l]]+a*sqr(sum[i]-sum[q[l]])+b*(sum[i]-sum[q[l]])+c; //按照我们推导出的式子，队头为最优。 while (l<r)and((f[q[r-1]]-f[q[r]]+a*(sqr(sum[q[r-1]])-sqr(sum[q[r]]))+b*(sum[q[r]]-sum[q[r-1]]))*(sum[q[r]]-sum[i])<=(f[q[r]]-f[i]+a*(sqr(sum[q[r]])-sqr(sum[i]))+b*(sum[i]-sum[q[r]]))*(sum[q[r-1]]-sum[q[r]])) do dec(r); //我们要找一个地方把新的f[i]插入队中（斜率优化里，每个元素进队一次出队一次），但是如果f[i]已经比队尾的某些元素更好的话，队尾的那些就不需要继续存在了。这而且句话是维护队尾从而保持队列单调性质的，当r-1,r,i上的元素不满足斜率递增时必然要调整。 inc(r); q[r]:=i; end; writeln(f[n]); //for i:=1 to n do write(f[i],' '); //close(input); close(output); end.