[BZOJ 3156] 防御准备

qwq

题意

给出n个防御节点,每个节点有两种选择,可以花费a[i]建立一个防御塔,或者放置一个木偶,木偶的花费为到右端第一个防御塔的距离。求最少花费。

思路

反转序列,搞出dp式子,斜率优化。

记得开longlong。

Code

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
#include <cstdio>
#include <cstring>
#include <cctype>
#include <algorithm>
typedef long long LL;
#define int LL
inline int getint()
{
int r = 0,s = 1;char c = getchar();for(;!isdigit(c);c = getchar()) if(c == '-') s = 0;
for(;isdigit(c);c = getchar()) r = (((r << 2) + r) << 1) + (c ^ '0');return s ? r : -r;
}
const int N = 1000010;
int Q[N],h = 0,t = 0;
int dp[N];int c[N],s[N];
int ans = 0x3f3f3f3f3f3f3f3f;int n;
inline int va(int i){return s[n] + dp[i] - s[i] - (n - i) * i;}
inline int b(int j){return dp[j] - s[j] + j * j + j;}
signed main()
{
n = getint();
for(int i = n;i;--i) c[i] = getint();
s[0] = 0;
dp[1] = c[1];
for(int i = 1;i <= n;i++) s[i] = s[i - 1] + i;
Q[h = t = 1] = 1;
ans = std::min(ans,va(1));
for(int i = 2;i <= n;i++)
{
while(h < t && (b(Q[h + 1]) - b(Q[h])) < i * (Q[h + 1] - Q[h])) h++;
dp[i] = dp[Q[h]] + s[i - 1] - s[Q[h]] - (i - Q[h] - 1) * Q[h] + c[i];
ans = std::min(ans,va(i));
while(h < t && (b(i) - b(Q[t])) * (Q[t] - Q[t - 1]) < (b(Q[t]) - b(Q[t - 1])) * (i - Q[t])) t--;
Q[++t] = i;
}
printf("%lld\n",ans);
return 0;
}