题目连接： http://new.tyvj.cn/Problem_Show.aspx?id=1215
思路：
方程再简单不过了：
dp[i]表示以第i个人为某一组最后一个人的总战斗值
dp[i]=max(dp[j]+F(sum[i]-sum[j]))
其中F(x)=A*x*x+B*x+C sum[i]表示战斗值的前缀和
显然n^2的方程，只能得到20分
单调性显然，那么就开始我们的斜率优化
设j<k且满足k比j更优
dp[j]+A*(sum[i]-sum[j])^2+B*(sum[i]-sum[j])+C<=dp[k]+A*(sum[i]-sum[k])^2+B*(sum[i]-sum[k])+C
化简,分离变量，将含j,k的结构放到方程一边，含i的结构放在方程另一边：
2*A*sum[i]*(sum[k]-sum[j])<=dp[k]-dp[j]+B*(sum[j]-sum[k])+A*(sum[k]^2-sum[j]^2)
设:
p[i]=2*A*sum[i]
G(k,j)=dp[k]-dp[j]+B*(sum[j]-sum[k])+A*(sum[k]^2-sum[j]^2)
S(k,j)=sum[k]-sum[j]
W(k,j)=G(k,j)/S(k,j)
所以只要维护 ： W(k,j)>=p[i] 就可以了~
（PS：如果没有看懂斜率优化，请转步： http://www.cnblogs.com/proverbs/archive/2012/10/06/2713109.html ）
View Code
1
#include <cstdio>
2
#include <cstring>
3
#include <cstdlib>
4
#include <iostream>
5
6
#define
N 1001000
7
8
using
namespace
std;
9
10
__int64 A,B,C,a[N],sum[N],dp[N],p[N];
11
int
n,q[N];
12
13
void
read()
14
{
15
scanf(
"
%d
"
,&
n);
16
scanf(
"
%I64d%I64d%I64d
"
,&A,&B,&
C);
17
for
(
int
i=
1
;i<=n;i++
)
18
{
19
scanf(
"
%I64d
"
,&
a[i]);
20
sum[i]=sum[i-
1
]+
a[i];
21
p[i]=
2
*A*
sum[i];
22
}
23
}
24
25
inline __int64 G(
int
y,
int
x)
26
{
27
return
dp[y]-dp[x]+B*(sum[x]-sum[y])+A*(sum[y]*sum[y]-sum[x]*
sum[x]);
28
}
29
30
inline __int64 S(
int
y,
int
x)
31
{
32
return
sum[y]-
sum[x];
33
}
34
35
inline __int64 F(
int
x)
36
{
37
return
A*x*x+B*x+
C;
38
}
39
40
void
go()
41
{
42
dp[
0
]=
0
;
43
int
h=
1
,t=
1
;
44
q[t++]=
0
;
45
for
(
int
i=
1
,x,y,z;i<=n;i++
)
46
{
47
while
(h<t-
1
&&G(q[h+
1
],q[h])>=p[i]*S(q[h+
1
],q[h])) h++
;
48
49
dp[i]=dp[q[h]]+F(sum[i]-
sum[q[h]]);
50
51
q[t++]=
i;
52
53
for
(
int
j=t-
2
;j-
1
>=h;j--
)
54
{
55
x=q[j-
1
]; y=q[j]; z=q[j+
1
];
56
if
(G(z,y)*S(y,x)>=G(y,x)*S(z,y)) q[j]=q[--
t];
57
else
break
;
58
}
59
}
60
printf(
"
%I64d\n
"
,dp[n]);
61
}
62
63
int
main()
64
{
65
read();
66
go();
67
return
0
;
68
}
