Time Limit: 4 Sec Memory Limit: 64 MB
Description
Input
Output
HINT
题目分析
斜率优化DP–详解
首先容易想到一个简单的
O
(
n
2
)
O(n^2)
O(n2)算法
d
p
[
i
]
dp[i]
dp[i]表示前
i
i
i个士兵分组能得到的最大战斗力
d
p
[
i
]
=
m
a
x
(
d
p
[
j
]
+
a
∗
(
s
u
m
[
i
]
−
s
u
m
[
j
]
)
2
+
b
∗
(
s
u
m
[
i
]
−
s
u
m
[
j
]
)
+
c
)
dp[i]=max(\ dp[j]+a*(sum[i]-sum[j])^2+b*(sum[i]-sum[j])+c\ )
dp[i]=max( dp[j]+a∗(sum[i]−sum[j])2+b∗(sum[i]−sum[j])+c )
然后把平方拆开，移项
d
p
[
j
]
+
a
∗
s
u
m
[
j
]
2
−
b
∗
s
u
m
[
j
]
=
2
a
∗
s
u
m
[
i
]
∗
s
u
m
[
j
]
−
a
∗
s
u
m
[
i
]
2
−
b
∗
s
u
m
[
i
]
−
c
+
d
p
[
i
]
dp[j]+a*sum[j]^2-b*sum[j]=2a*sum[i]*sum[j]-a*sum[i]^2-b*sum[i]-c+dp[i]
dp[j]+a∗sum[j]2−b∗sum[j]=2a∗sum[i]∗sum[j]−a∗sum[i]2−b∗sum[i]−c+dp[i] 以
d
p
[
j
]
+
a
∗
s
u
m
[
j
]
2
−
b
∗
s
u
m
[
j
]
dp[j]+a*sum[j]^2-b*sum[j]
dp[j]+a∗sum[j]2−b∗sum[j]为
y
y
y，
s
u
m
[
j
]
sum[j]
sum[j]为
x
x
x，
2
a
∗
s
u
m
[
i
]
2a*sum[i]
2a∗sum[i]为斜率进行斜率优化即可
注意此题所求是最大值，单调队列维护的是斜率单调递减的上凸壳
#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<cstring>
#include<cstdio>
using namespace std
;
typedef long long lt
;
typedef double dd
;
#define sqr(x) ((x)*(x))
lt
read()
{
lt f
=1,x
=0;
char ss
=getchar();
while(ss
<'0'||ss
>'9'){if(ss
=='-')f
=-1;ss
=getchar();}
while(ss
>='0'&&ss
<='9'){x
=x
*10+ss
-'0';ss
=getchar();}
return f
*x
;
}
const int maxn
=2000010;
lt n
,a
,b
,c
;
lt sum
[maxn
],dp
[maxn
];
int q
[maxn
],ll
,rr
;
lt
qans(int i
,int j
){ return dp
[j
]+a
*sqr(sum
[j
])-b
*sum
[j
]-2*a
*sum
[i
]*sum
[j
]+a
*sqr(sum
[i
])+b
*sum
[i
]+c
;}
dd
calc(int j1
,int j2
)
{
lt ty
=(dp
[j2
]+a
*sqr(sum
[j2
])-b
*sum
[j2
])-(dp
[j1
]+a
*sqr(sum
[j1
])-b
*sum
[j1
]);
lt tx
=sum
[j2
]-sum
[j1
];
return (dd
)ty
/(dd
)tx
;
}
int main()
{
n
=read();a
=read();b
=read();c
=read();
for(int i
=1;i
<=n
;++i
)
{
int x
=read();
sum
[i
]=sum
[i
-1]+x
;
}
ll
=rr
=1;
for(int i
=1;i
<=n
;++i
)
{
while( ll
<rr
&& calc(q
[ll
],q
[ll
+1]) >= 2*a
*sum
[i
] ) ++ll
;
dp
[i
]=qans(i
,q
[ll
]);
while( ll
<rr
&& calc(q
[rr
-1],q
[rr
]) <= calc(q
[rr
],i
) ) --rr
;
q
[++rr
]=i
;
}
printf("%lld",dp
[n
]);
return 0;
}
