APIO10

Apio-10-特别行动队
【题目描述】
你有一支由n名预备役士兵组成的部队，士兵从1到n编号，要将他们拆分成若干特别行动队调入战场。出于默契的考虑，同一支特别行动队中队员的编号应该连续，即为形如(i, i + 1, …, i + k)的序列。 编号为i的士兵的初始战斗力为xi ，一支特别行动队的初始战斗力x为队内士兵初始战斗力之和，即x = xi + xi+1 + … + xi+k。 通过长期的观察，你总结出一支特别行动队的初始战斗力x将按如下经验公式修正为x'：x' = ax^2 + bx + c，其中a, b, c是已知的系数（a < 0）。 作为部队统帅，现在你要为这支部队进行编队，使得所有特别行动队修正后战斗力之和最大。试求出这个最大和。 例如，你有4名士兵，x1 = 2, x2 = 2, x3 = 3, x4 = 4。经验公式中的参数为a = –1, b = 10, c = –20。此时，最佳方案是将士兵组成3个特别行动队：第一队包含士兵1和士兵2，第二队包含士兵3，第三队包含士兵4。特别行动队的初始战斗力分别为4, 3, 4，修正后的战斗力分别为4, 1, 4。修正后的战斗力和为9，没有其它方案能使修正后的战斗力和更大。
【输入格式】
输入由三行组成。第一行包含一个整数n，表示士兵的总数。第二行包含三个整数a, b, c，经验公式中各项的系数。第三行包含n个用空格分隔的整数x1, x2, …, xn，分别表示编号为1, 2, …, n的士兵的初始战斗力。
【数据范围】
20%的数据中，n ≤ 1000； 50%的数据中，n ≤ 10,000； 100%的数据中，1 ≤ n ≤ 1,000,000，–5 ≤ a ≤ –1，|b| ≤ 10,000,000，|c| ≤ 10,000,000，1 ≤ xi ≤ 100。

【输出格式】

输出一个整数，表示所有特别行动队修正后战斗力之和的最大值。
【样例输入】

4 -1 10 -20 2 2 3 4

【样例输出】

9

============================================================================================
头一次把分析写的这么细致，因为这题实在是很不错~
另外再说点细节上的问题，Que之类的数据结构虽然小但是模块化一下绝不是浪费时间，读起来巨清晰！
============================================================================================
贴代码：

program Commando;
const MaxN=1000000;
var S,F,G,L:array[0..MaxN] of double;//用Double的目的：一是为了防止数据溢出，二是为了避免纠结整除法的取整问题A,B,C:double;N:longint;Que:array[0..MaxN] of longint;Top,Last:longint;
//Que
procedure Que_SetEmpty;
begin Top:=0; Last:=0;
end;
function Que_Size:longint;
begin exit(Last-Top);
end;
function Que_Top(i:longint):longint;
begin exit(Que[Top+i]);
end;
function Que_Last(i:longint):longint;
begin exit(Que[Last-i+1]);
end;
procedure Que_Push(i:longint);
begin inc(Last); Que[Last]:=i;
end;
procedure Que_DelTop;
begin inc(Top);
end;
procedure Que_DelLast;
begin dec(Last);
end;
//End of Que//Init
procedure Init;
var i,x,ta,tb,tc:longint;
begin readln(N);readln(ta,tb,tc);A:=ta; B:=tb; C:=tc;S[0]:=0; G[0]:=0;for i:=1 to N do beginread(x);S[i]:=S[i-1]+x;G[i]:=(A*S[i]-B)*S[i];L[i]:=2*A*S[i];end;
end;
//End of Init//Math
function K(i,j:longint):double;
begin K:=(F[i]+G[i]-F[j]-G[j])/(S[i]-S[j]);
end;
function Q(x:double):double;
begin exit((A*x+B)*x+C);//这里有个多项式计算的小技巧，可以降低常数！
end;
//End of Math//Solve
procedure Solve;
var i:longint;
begin Que_SetEmpty;Que_Push(0); F[0]:=0;for i:=1 to N do beginwhile Que_Size>1 doif K(Que_Top(1),Que_Top(2))>L[i] then Que_DelTopelse break;F[i]:=F[Que_Top(1)]+Q(S[i]-S[Que_Top(1)]); //writeln(F[i]:0:0,',',Que_Top(1));while Que_Size>1 doif K(Que_Last(2),Que_Last(1))<=K(Que_Last(1),i) then Que_DelLastelse break;Que_Push(i);end;write(F[N]:0:0);
end;
//End of Solve//Main
procedure Main;
begin Init;Solve;
end;
//End of Main
begin Assign(input,'commando.in'); reset(input);Assign(output,'commando.out'); rewrite(output);Main;close(input); close(output);
end.

============================================================================================
单调队列，斜率优化是很强大的优化方法，一定要细致分析题目！