【BZOJ 1191】 [Apio2010]特别行动队（斜率优化）

dsy1911: [Apio2010]特别行动队

【题目描述】

有n个数，分成连续的若干段，每段的分数为a*x^2+b*x+c（a，b，c是给出的常数），其中x为该段的各个数的和。求如何分才能使得各个段的分数的总和最大。

【输入格式】

第1行:1个整数N (1 <= N <= 1000000)。

第2行：3个整数a，b，c（-5<=a<=-1,|b|<=10000000,|c|<=10000000

下来N个整数，每个数的范围为[1,100]。

【输出格式】

一个整数，各段分数总和的值最大。

【分析】

　　设s[i]为i的前缀和。

　　dp方程： f[i]=f[j]+a*(s[i]-s[j])^2+b(s[i]-s[j])+c

　　即 f[i]=-2a*s[i]*s[j]+a*s[j]^2-b*s[j]+f[j]+a*s[i]^2+b*s[i]+c

　　化成斜率优化标准形式，维护一个右上凸包即可。

代码如下：

 1 #include<cstdio>
 2 #include<cstdlib>
 3 #include<cstring>
 4 #include<iostream>
 5 #include<algorithm>
 6 #include<queue>
 7 #include<cmath>
 8 using namespace std;
 9 #define Maxn 1000010
10 #define LL long long
11 
12 LL w[Maxn],s[Maxn];
13 LL a,b,c;
14 
15 struct node
16 {
17     LL x,y;
18 }t[Maxn];int len=0;
19 
20 LL f[Maxn];
21 
22 bool check(int x,int y,int k)
23 {
24     LL kk=k;
25     return kk*(t[y].x-t[x].x)<=(t[y].y-t[x].y);
26 }
27 
28 bool check2(int x,int y,int z)
29 {
30     return (t[z].x-t[y].x)*(t[y].y-t[x].y)<=(t[y].x-t[x].x)*(t[z].y-t[y].y);
31 }
32 
33 int main()
34 {
35     int n;
36     scanf("%d",&n);
37     scanf("%lld%lld%lld",&a,&b,&c);
38     s[0]=0;
39     for(int i=1;i<=n;i++)
40     {
41         scanf("%lld",&w[i]);
42         s[i]=s[i-1]+w[i];
43     }
44     int st;
45     t[++len].x=0;t[len].y=0;st=1;
46     for(int i=1;i<=n;i++)
47     {
48         while(st<len&&check(st,st+1,2*a*s[i])) st++;
49         f[i]=-2*a*s[i]*t[st].x+t[st].y+a*s[i]*s[i]+b*s[i]+c;
50         t[0].x=s[i];t[0].y=a*s[i]*s[i]-b*s[i]+f[i];
51         while(st<len&&check2(len-1,len,0)) len--;
52         t[++len]=t[0];
53     }
54     printf("%lld
",f[n]);
55     return 0;
56 }

[BZOJ 1911]

2016-09-19 20:45:07

【BZOJ 1191】 [Apio2010]特别行动队 （斜率优化）

【BZOJ 1191】 [Apio2010]特别行动队（斜率优化）