Bzoj 1010(斜率优化DP)

BZOJ 1010
见此讲解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<queue>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
using namespace std;
LL n, P, dp[50005], s[50005];
LL l, r, que[150005];
inline db getK(int k, int j) {return (db)(dp[k] - dp[j] + (s[k] + P) * (s[k] + P) - (s[j] + P) * (s[j] + P)) / (2.0 * (db)(s[k] - s[j]));}
//计算两个点之间斜率
void clean() {}
int solve() {
clean();
scanf("%lld%lld", &n, &P), s[0] = 0, P++;
for (int i = 1; i <= n; i++) scanf("%lld", &s[i]), s[i] += s[i - 1];
for (int i = 1; i <= n; i++) s[i] += i;
dp[1] = 0, l = 1, r = 1; //原点是决策点 r必须为1
for (int i = 1; i <= n; i++) {
while (l < r && getK(que[l], que[l + 1]) <= (db)s[i]) l++;
//l必须严格小于r,因为单调队列中要有两个元素
dp[i] = dp[que[l]] + (s[i] - s[que[l]] - P) * (s[i] - s[que[l]] - P);
while (l < r && getK(que[r - 1], que[r]) >= getK(que[r], i)) r--;
que[++r] = i;
}
printf("%lld\n", dp[n]);
return 0;
}
int main() {
solve();
return 0;
}

------ 本文结束 ------