一道不错的斜率优化入门题，传送门：bzoj 1911

题目描述稍微有点不太清楚，先解释一下

将n个士兵分成几个连续的组，每一组的战斗力为f(y),其中：f(x)=ax²+bx+c（a，b，c题中已给）,y为这一组中士兵战斗力之和，求这几个组的战斗力之和的最大值。

考虑dp，设dp[x]表示将前x个士兵分组后所得到的战斗力的最大值

设v[i]为士兵i的战斗力，则有dp方程：

很明显，方程中的可以用前缀和优化，设s[i]为到第i个士兵的战力之和，则dp方程变为：

 

然而复杂度还是n²的，看一下数据范围，n≤1000000,枚举必然TLE，我们需要更好的的办法，处理一下dp方程，把右侧乘开，

我们惊奇的发现，右侧出现了一些只与i有关的项，我们把它移到左边，在稍加整理，将C移项后，得到：

现在，我们把它变成一条直线，令：

k=s[i]

b=dp[i]-As[i]²-Bs[i]-C

x=2As[j]

y=dp[j]+As[j]²-Bs[j]

这样，这条直线便只与i有关了，要求dp[i]，就是求b的最大值，因而，我们产生了一种新的策略，在一个平面直角坐标系上，记录一系列的点，并从这些点中选取一个最优的，但这样好像还是n²的啊

别怕，我们可以进一步优化，

首先，很明显的一点是，最优的点一定在凸包上，不在凸包上的点便可以直接排除

其次，由于战力大于0，因而k会单调递增，这样，就可以每次将斜率小于k的点全部排除，这样，使用单调队列维护凸包，每算出一个点就将其推入队列，便可O(1)找出最优的j了，便成功的优化成了O(n)

谨此献上代码

 1 #include<cstdio>
 2 int n,a,b,c,head,tail;
 3 long long val[1001000],pre[1001000],que[1001000],dp[1001000];
 4 inline long long getx(long long v)
 5 {
 6     return 2*a*pre[v];
 7 }
 8 inline long long gety(long long v)
 9 {
10     return dp[v]+a*pre[v]*pre[v]-b*pre[v];
11 }
12 inline long long getdp(long long aa,long long bb)
13 {
14     return dp[bb]+a*pre[bb]*pre[bb]-b*pre[bb]-2*a*pre[aa]*pre[bb]+a*pre[aa]*pre[aa]+b*pre[aa]+c;
15 }
16 inline double getk(long long aa,long long bb)
17 {
18     return ((double)(gety(aa)-gety(bb)))/((double)(getx(aa)-getx(bb)));
19 }
20 int main()
21 {
22     scanf("%d%d%d%d",&n,&a,&b,&c);
23     for(int i=1;i<=n;i++)
24     {
25         scanf("%d",&val[i]);
26         pre[i]=pre[i-1]+val[i];
27     }
28     for(int i=1;i<=n;i++)
29     {
30         while(head<tail&&getk(que[head],que[head+1])<=pre[i])
31         {
32             head++;
33         }
34         dp[i]=getdp(i,que[head]);
35         while(head<tail&&getk(i,que[tail])<=getk(que[tail],que[tail-1]))
36         {
37             tail--;
38         }
39         que[++tail]=i;
40     }
41     printf("%d\n",dp[n]);
42     return 0;
43 }