一道不错的斜率优化入门题,传送门: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/
转载文章受原作者版权保护。转载请注明原作者出处!