OI题解 - Jump mission(Codechef)

2020到了呢……忽然想起来2019咕了好多题解 awa

趁放这一天假补一发~


# 题意

有 $n$ 座山从左到右依次排列,大厨要从第一座山“跳”到第 $n$ 座。第 $i$ 座山的高度为 $h_i$,且大厨给了每座山一个数值 $p_i$。另外,当大厨到达第 $i$ 座山时,他会花费 $a_i$ 的代价做一顿饭(大厨在第一座山也会做一顿饭)。

大厨能从第 $i$ 座山跳到第 $j$ 座山当且仅当 $i<j$ 且 $p_i<p_j$,代价为 $(h_i,-h_j)^2$。

数据规模:

  • $2\le n\le3\times10^5$
  • $p_i$ 是 1~n 的一个排列,且 $p_1=1,p_n=n$
  • $|a_i|\le10^9$
  • $1\le h_i\le6\times10^5$

# 解析

DP思路并不难,定义 $f_i$ 表示跳到第 $i$ 座山的最小总代价,那么 $f_1=a_1$。转移式也很简单:

思维比较敏锐的reader应该能够注意到转移式中有 $i,j$ 的乘积项,显然是可以凸包优化 的(拒绝斜率优化……)

直线的斜率就是 $-2h_j$,截距就是 $f_j+2h_j^2$,横坐标就是 $h_i$。
然后非常开心地发现,斜率、横坐标都不单调……那就李超线段树 吧,因为 $h_i\in[1,6\times10^5]$,也可以不离散化(之前眼瞎以为是 $10^9$ 的范围,还写了个离散化 awa)

但是发现对于转移点 $j$ 还有一个 $p_j< p_i$ 的限制,只用李超线段树并不能处理这种限制。其实不难发现,这个限制比较类似于“前缀和”—— $j$ 只会对 $p_i\ge p_j$ 的 $i$ 产生影响。于是动态维护前缀信息的常用办法——树状数组

树状数组的每个节点就是一棵李超线段树,下标是 $p_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
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
91
92
93
94
95
96
97
98
99
100
101
/*Lucky_Glass*/
#include<vector>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int N=3e5,M=6e5;
typedef long long ll;

int n,m;
int P[N+3],A[N+3],H[N+3];
ll f[N+3];
vector<int> uni;

#define lowbit(i) (i&-i)
#define ek(i) (-2ll*H[i])
#define eb(i) (1ll*H[i]*H[i]+f[i])

ll Calc(int i,ll Dx){return ek(i)*Dx+eb(i);}

struct NODE{
int id;
NODE *ch[2];
};
struct SEGTREE{
NODE nod[N*200],*root[N+3],*ncnt;
SEGTREE(){ncnt=nod;}
NODE* NewNode(){
NODE *p=++ncnt;
p->id=0;
p->ch[0]=p->ch[1]=NULL;
return p;
}
void Insert(NODE *&u,int lef,int rig,int now){
if(!u) u=NewNode();
if(!u->id){u->id=now;return;}
int &org=u->id;
if(Calc(org,uni[lef])>=Calc(now,uni[lef]) && Calc(org,uni[rig])>=Calc(now,uni[rig])) {org=now;return;}
if(Calc(org,uni[lef])<=Calc(now,uni[lef]) && Calc(org,uni[rig])<=Calc(now,uni[rig])) return;
if(Calc(org,uni[lef])>Calc(now,uni[lef])) swap(org,now);
int mid=(lef+rig)>>1;
if(Calc(org,uni[mid])>Calc(now,uni[mid]))
swap(org,now),Insert(u->ch[0],lef,mid,now);
else
Insert(u->ch[1],mid+1,rig,now);
}
void Insert(int i){
int pos=P[i];
while(pos<=n){
Insert(root[pos],1,m,i);
pos+=lowbit(pos);
}
}
int Query(NODE *u,int lef,int rig,int pos){
if(!u) return 0;
if(lef==rig) return u->id;
int mid=(lef+rig)>>1,resu;
if(pos<=uni[mid]) resu=Query(u->ch[0],lef,mid,pos);
else resu=Query(u->ch[1],mid+1,rig,pos);
if(!resu) return u->id;
if(!u->id) return resu;
if(Calc(resu,pos)<Calc(u->id,pos)) return resu;
return u->id;
}
int Query(int i){
int resu=0,pos=P[i];
while(pos){
int cur=Query(root[pos],1,m,H[i]);
if(cur){
if(!resu) resu=cur;
else if(Calc(cur,H[i])<Calc(resu,H[i])) resu=cur;
}
pos-=lowbit(pos);
}
return resu;
}
}Se;

int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&P[i]);
for(int i=1;i<=n;i++) scanf("%d",&A[i]);
for(int i=1;i<=n;i++){
scanf("%d",&H[i]);
uni.push_back(H[i]);
}
uni.push_back(-1);
sort(uni.begin(),uni.end());
uni.erase(unique(uni.begin(),uni.end()),uni.end());
m=uni.size()-1;
f[1]=A[1];
Se.Insert(1);
for(int i=2;i<=n;i++){
int j=Se.Query(i);
f[i]=f[j]+1ll*(H[i]-H[j])*(H[i]-H[j])+A[i];
Se.Insert(i);
}
printf("%lld\n",f[n]);
return 0;
}

The End

Thanks for reading!

2020快乐~(都不知道说些什么好了 :<)

0%