APIO2010 特别行动队

P2407 - 【APIO2010】特别行动队

Description

你有一支由 n 名预备役士兵组成的部队，士兵从 1 到 n 编号，要将他们拆分成若干特别行动队调入战场。出于默契的考虑，同一支特别行动队中队员的编号应该连续，即为形如(i, i + 1, …, i + k)的序列。
编号为 i 的士兵的初始战斗力为 xi ，一支特别行动队的初始战斗力 x 为队内士兵初始战斗力之和，即 X = Xi + Xi+1 + … + Xi+k。通过长期的观察，你总结出一支特别行动队的初始战斗力 x 将按如下经验公式修正为 x'： x' = ax^2 + bx + c，其中 a, b, c 是已知的系数（ a < 0）。
作为部队统帅，现在你要为这支部队进行编队，使得所有特别行动队修正后战斗力之和最大。试求出这个最大和。
例如，你有 4 名士兵， x1 = 2, x2 = 2, x3 = 3, x4 = 4。经验公式中的参数为 a = –1,b = 10, c = –20。此时，最佳方案是将士兵组成 3 个特别行动队：第一队包含士兵1 和士兵 2，第二队包含士兵 3，第三队包含士兵 4。特别行动队的初始战斗力分别为 4, 3, 4，修正后的战斗力分别为 4, 1, 4。修正后的战斗力和为 9，没有其它方案能使修正后的战斗力和更大。

Input

输入由三行组成。第一行包含一个整数 n，表示士兵的总数。第二行包含三个整数 a, b, c，经验公式中各项的系数。第三行包含 n 个用空格分隔的整数 x1,x2, …, xn，分别表示编号为 1, 2, …, n 的士兵的初始战斗力。

Output

输出一个整数，表示所有特别行动队修正后战斗力之和的最大值。

Sample Input

4
-1 10 -20
2 2 3 4

Sample Output

Hint

20%的数据中， n ≤ 1000；
50%的数据中， n ≤ 10,000；
100%的数据中， 1 ≤ n ≤ 1,000,000， –5 ≤ a ≤ –1， |b| ≤ 10,000,000， |c| ≤10,000,000， 1 ≤ xi ≤ 100。

Source

APIO，斜率优化，动态规划

简单方程斜率优化，dp[i]=max(dp[j] + a*(C[i]-C[j])^2 + b*(C[i]-C[j])+c);最关键的一点，除法有精度差！！！！！！，ｇｅｔｘ（）函数修改为ｃａｌｅ（l1,l2,l3）函数，相乘计算，不用除法：

 1 #include<algorithm>
 2 //#include<iostream>
 3 #include<iomanip>
 4 #include<cstdlib>
 5 #include<cstring>
 6 #include<cstdio>
 7 #include<vector>
 8 #include<cmath>
 9 #include<queue>
10 #include<stack>
11 #include<map>
12 #include<set>
13 #define ll long long
14 #define inf 1<<30
15 #define rep(i,a,b) for(register int i=a;i<=b;++i)
16 #define re register
17 using namespace std;
18 const int N=1000011;
19 ll C[N],dp[N],a,b,c;
20 int q[N];
21 int n;
22 inline ll gi( )
23 {
24     register ll ret=0,f=1;char ch=getchar();
25     while((ch<'0'||ch>'9')&&(ch!='-')) ch=getchar();
26     if(ch=='-') f=-1,ch=getchar();
27     while(ch>='0'&&ch<='9') ret=ret*10+ch-'0',ch=getchar();
28     return ret*f;
29 }
30 inline ll getnum(int i,int k) {
31     register ll u=C[i]-C[k];
32     return dp[k]+a*u*u+b*u+c;
33 }
34 inline bool cale(int l1,int l2,int l3) {
35     register  ll b1=dp[l1]+a*C[l1]*C[l1]-b*C[l1],b2=dp[l2]+a*C[l2]*C[l2]-b*C[l2],b3=dp[l3]+a*C[l3]*C[l3]-b*C[l3];
36     register ll k1=-2*a*C[l1],k2=-2*a*C[l2],k3=-2*a*C[l3];
37     return (b3-b2)*(k1-k2) <= (b2-b1) * (k2-k3);//   ¾«¶È²î¿ÓÁËÎÒ£¡£¡£¡ 
38 }
39 int main( )
40 {
41     n=gi();a=gi(),b=gi(),c=gi();
42     rep(i,1,n) C[i]=gi(),C[i]+=C[i-1];
43     q[0]=0;
44     q[1]=1;
45     dp[0]=0;
46     dp[1]=a*C[1]*C[1]+b*C[1]+c;
47     register int hd=0,tl=1;
48     rep(i,2,n) {
49         while(hd+2<=tl&&cale(q[tl-2],q[tl-1],q[tl])) q[tl-1]=q[tl--];// bug <= 
50         while(hd<tl&&getnum(i,q[hd])<=getnum(i,q[hd+1])) hd++;
51         dp[i]=getnum(i,q[hd]);
52         q[++tl]=i;
53     }
54     printf("%lld",dp[n]);
55     return 0;
56 }