bzoj 1191 特别行动队

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

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

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

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

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

bzoj 1191 特别行动队

很明显,方程中的bzoj 1191 特别行动队可以用前缀和优化,设s[i]为到第i个士兵的战力之和,则dp方程变为:

 bzoj 1191 特别行动队

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

bzoj 1191 特别行动队

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

bzoj 1191 特别行动队

现在,我们把它变成一条直线,令:

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<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 }

 

上一篇:1191:流感传染


下一篇:1191:流感传染