OI题解 - Jump mission(Codechef) | Lucky_Glass's Blog

以心为名，名为爱惜

0%

OI题解 - Jump mission(Codechef)

发表于 分类于 Valine：

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快乐~（都不知道说些什么好了 :<）