一道不错的斜率优化入门题，传送门：bzoj 1911
题目描述稍微有点不太清楚，先解释一下
将n个士兵分成几个连续的组，每一组的战斗力为f(y),其中：f(x)=ax2+bx+c（a，b，c题中已给）,y为这一组中士兵战斗力之和，求这几个组的战斗力之和的最大值。
考虑dp，设dp[x]表示将前x个士兵分组后所得到的战斗力的最大值
设v[i]为士兵i的战斗力，则有dp方程：
然而复杂度还是n2的，看一下数据范围，n≤1000000,枚举必然TLE，我们需要更好的的办法，处理一下dp方程，把右侧乘开，
我们惊奇的发现，右侧出现了一些只与i有关的项，我们把它移到左边，在稍加整理，将C移项后，得到：
现在，我们把它变成一条直线，令：
k=s[i]
b=dp[i]-As[i]2-Bs[i]-C
x=2As[j]
y=dp[j]+As[j]2-Bs[j]
这样，这条直线便只与i有关了，要求dp[i]，就是求b的最大值，因而，我们产生了一种新的策略，在一个平面直角坐标系上，记录一系列的点，并从这些点中选取一个最优的，但这样好像还是n2的啊
别怕，我们可以进一步优化，
首先，很明显的一点是，最优的点一定在凸包上，不在凸包上的点便可以直接排除
其次，由于战力大于0，因而k会单调递增，这样，就可以每次将斜率小于k的点全部排除，这样，使用单调队列维护凸包，每算出一个点就将其推入队列，便可O(1)找出最优的j了，便成功的优化成了O(n)
谨此献上代码
1 #include
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)
24 {
25 scanf("%d",&val[i]);
26 pre[i]=pre[i-1]+val[i];
27 }
28 for(int i=1;i)
29 {
30 while(head1])pre[i])
31 {
32 head++;
33 }
34 dp[i]=getdp(i,que[head]);
35 while(head1]))
36 {
37 tail--;
38 }
39 que[++tail]=i;
40 }
41 printf("%d\n",dp[n]);
42 return 0;
43 }
Original: https://www.cnblogs.com/Grharris/p/10371835.html
Author: Grharris
Title: bzoj 1191 特别行动队
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/578008/
转载文章受原作者版权保护。转载请注明原作者出处！