隐藏
「JZOJ3859」孤独一生 - 动态规划+树状数组 | Bill Yang's Blog

路终会有尽头,但视野总能看到更远的地方。

0%

「JZOJ3859」孤独一生 - 动态规划+树状数组

题目大意

    下课了,Polo来到球场,但他到了之后才发现…被放了飞机…
    无事可做的他决心找点乐子,比方说……跳台阶……
    球场边有N个台阶拍成一行,第$i$个台阶的高度是$H_i(0\lt H_i\le10^9)$,第$0$个台阶,也就是地面的高度为$0$。Polo打算把这$N$个台阶分成两个集合$S_a,S_b$(可以为空),对于一个台阶集合$S=\lbrace P_1,P_2,…P_{|S|}\rbrace$,其中$P_1\lt P_2\lt\ldots\lt P_{|S|}$,他需要花费$\sum_{i=1}^{|S|}|H_{p_i}-H_{p_{i-1}}|$的体力值来完成。
    现在他希望两次跳跃所需的总体力值最小,你能帮帮他吗?


题目分析

我们可以分别设状态将两个集合的末尾位置表示出来并互相转移。
但是写出的状态转移方程竟然一模一样!

仔细分析也可发现,其实分的是哪个集合对本题并无影响,真正带来影响的是集合的分割点。

设$f[i]$表示在$i$之前进行分割,将$i$以后的分割出来的最小代价。

因此:

其中,$sum[]$是差绝对值的前缀和。

然后就可以写出$50$分的暴力了。

$100$分我们可以采用树状数组优化动态规划方程。
将绝对值拆开,用树状数组分别维护$f[i]-sum[i]-a[i-1]$与$f[i]-sum[i]+a[i-1]$即可。

树状数组的维护方式是:维护两个树状数组,一个表示比$a[i]$更小$a[j-1]$的$f[j]-sum[j]-a[j-1]$的值,另一个反之。

因此我们可以用$a[]$作下标建立树状数组,需要事先离散化。


代码

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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<climits>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;

typedef long long LL;

inline const LL Get_Int() {
LL num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}

const int maxn=500005;
int n;
LL a[maxn],sum[maxn],f[maxn],tmp[maxn],b[maxn];

struct BIT1 {
LL c[maxn];
#define lowbit(x) x&-x
BIT1() {
memset(c,0x7f,sizeof(f));
}
void add(int x,LL v) {
for(int i=x; i<=n+1; i+=lowbit(i))c[i]=min(c[i],v);
}
LL ask(int x) {
LL ans=LLONG_MAX/2;
for(int i=x; i>=1; i-=lowbit(i))ans=min(ans,c[i]);
return ans;
}
} bit1;

struct BIT2 {
LL c[maxn];
#define lowbit(x) x&-x
BIT2() {
memset(c,0x7f,sizeof(f));
}
void add(int x,LL v) {
for(int i=x; i>=1; i-=lowbit(i))c[i]=min(c[i],v);
}
LL ask(int x) {
LL ans=LLONG_MAX/2;
for(int i=x; i<=n+1; i+=lowbit(i))ans=min(ans,c[i]);
return ans;
}
} bit2;

void Discretization(LL* a) {
memcpy(b,a,sizeof(b));
sort(a+1,a+n+1);
int cnt=unique(a+1,a+n+1)-a-1;
for(int i=1; i<=n; i++)b[i]=lower_bound(a+1,a+cnt+1,b[i])-a+1;
}

int main() {
n=Get_Int();
for(int i=1; i<=n; i++) {
a[i]=Get_Int();
tmp[i]=a[i];
sum[i]=sum[i-1]+abs(a[i]-a[i-1]);
}
Discretization(tmp);
b[0]=1;
for(int i=1; i<=n; i++) {
if(i==1)f[1]=a[1];
else f[i]=min(bit1.ask(b[i])+sum[i-1]+a[i],bit2.ask(b[i])+sum[i-1]-a[i]);
bit1.add(b[i-1],f[i]-sum[i]-a[i-1]);
bit2.add(b[i-1],f[i]-sum[i]+a[i-1]);
}
for(int i=1; i<=n; i++)f[n]=min(f[n],f[i]+sum[n]-sum[i]);
printf("%lld\n",f[n]);
return 0;
}
姥爷们赏瓶冰阔落吧~