題目連接： 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
}
?
?
?
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
