「BZOJ3156」防御准备

Description

Input

第一行为一个整数NN表示战线的总长度。
第二行NN个整数,第ii个整数表示在位置ii放置守卫塔的花费AiA_i

Output

共一个整数,表示最小的战线花费值。

Sample Input

1
2
10
2 3 1 5 4 5 6 3 1 2

Sample Output

1
18

HINT

1N106,1Ai1091\leq N\leq 10^6,1\leq Ai\leq 10^9

Solution

为了方便,序列倒序一下。
f[i][0]f[i][0]ii点不放守卫
f[i][1]f[i][1]ii点放守卫

f[i][0]=max{f[j][1]+(ij+1)(ij)/2}(j[1,i1])f[i][0] = max\{f[j][1] + (i - j + 1) * (i - j) / 2\}(j\in [1,i-1])
f[i][1]=f[i1][0]+a[i]f[i][1] = f[i - 1][0] + a[i]

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
36
37
38
39
40
41
42
43
44
45
46
47
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<map>
#include<cmath>
#include<queue>
#include<bitset>
#define mk make_pair
#define fi first
#define nd second
#define pii pair<int,int>
#define pb push_back
#define sqr(x) ((x)*(x))
using namespace std;
typedef long long ll;
inline ll read() {ll x = 0; char ch = getchar(), w = 1;while(ch < '0' || ch > '9') {if(ch == '-') w = -1;
ch = getchar();}while(ch >= '0' && ch <= '9') {x = x * 10 + ch - '0';ch = getchar();}return x * w;}
void write(ll x) {if(x < 0) putchar('-'), x = -x;if(x > 9) write(x / 10);putchar(x % 10 + '0');}
inline void writeln(ll x) {write(x);puts("");}
const int N = 1e6 + 6;
ll a[N];
int n;
ll f[N][2];
int q[N], h, t;
double F(ll x) {
return (double)(sqr(x) - x + 2 * f[x][1]) / 2;
}
double slope(int x, int y) {
return (double)(F(y) - F(x)) / (y - x);
}
int main() {
n = read();
for(int i = 1; i <= n; ++i) a[n - i + 1] = read();
memset(f,0x3f,sizeof f);
f[1][1] = a[1];
q[h = t = 1] = 1;
for(int i = 2; i <= n; ++i) {
while(h < t && slope(q[h], q[h + 1]) <= i) ++h;
f[i][0] = f[q[h]][1] + (ll)(i - q[h] + 1) * (i - q[h]) / 2;
f[i][1] = min(f[i - 1][0], f[i - 1][1]) + a[i];
while(h < t && slope(q[t - 1], q[t]) >= slope(q[t - 1], i)) --t;
q[++t] = i;
}
writeln(min(f[n][0], f[n][1]));
return 0;
}