P8726 [蓝桥杯 2020 省 AB3] 旅行家 题解

· · 题解

P8726 [蓝桥杯 2020 省 AB3] 旅行家 题解

题面大意

其实题面还挺好懂的，不像以前 APIO 的某些题目那么谜语。

传送门。

解题思路

20pts 的部分分

### 70pts 的部分分 依据题面，可以轻易得出以下的状态转移方程： 记 $f_i$ 为到达第 $i$ 个岛屿（而且没有走）时所剩下 RP 的最大值。$f_1$ 初始化为 $0$。 由此可得： $$f_i=\min_{1\le j<i}\left\lfloor\dfrac{f_j}{2}\right\rfloor+T_iT_j-F_j$$ 暴力枚举 $i,j$ 转移即可，时间复杂度 $O(n^2)$。 ### 正解 对上述状态转移方程，考虑斜率优化。 假定 $i$ 已确定。 记 $f_i\gets y,k=T_j,x=T_i,b=\left\lfloor\dfrac{f_j}{2}\right\rfloor-F_j

由于要最大化 f_i，那么问题转化为：对于当前的若干条直线 y=kx+b，求它们在横坐标为 x 时，纵坐标的最大值。

使用李超线段树（LCT）来维护以上信息。

对李超线段树不了解或不熟练的同学，可以先去看这道模板题，并特别推荐这篇题解，讲得非常简洁清晰。

每求出一个 f_i，就把新的直线 y=kx+b 甩进去，要用的时候直接查询即可。

记得把所有节点的区间优势线段初始化为 y=-\infty（一般用一个极小值去表示），不然可能会 WA！

时间复杂度为 O(n\log n)，可以通过本题。

参考代码

#include<algorithm>
#include<iostream>
#include<cmath>
using namespace std;
#define int long long
const int INF=0x3f3f3f3f3f3f3f3f;
const int N=5e5+10;
struct ccf{
    int k,b;
    friend bool operator==(ccf pre,ccf nxt){
        return pre.k==nxt.k&&pre.b==nxt.b;
    }
}ln[4*N];
struct node{
    int l,r,bst;
}tree[N];
void build(int pos,int lft,int rgt){
    tree[pos].l=lft;
    tree[pos].r=rgt;
    if(lft==rgt) return;
    int mid=(lft+rgt)/2;
    build(pos*2,lft,mid);
    build(pos*2+1,mid+1,rgt);
}
void upd(int pos,int num){
    int mid=(tree[pos].l+tree[pos].r)/2;
    if(ln[num]==ln[tree[pos].bst]) return;
    if(ln[num].k*mid+ln[num].b>ln[tree[pos].bst].k*mid+ln[tree[pos].bst].b) swap(tree[pos].bst,num);
    if(tree[pos].l==tree[pos].r) return;
    if(ln[num].k*tree[pos].l+ln[num].b>=ln[tree[pos].bst].k*tree[pos].l+ln[tree[pos].bst].b) upd(pos*2,num);
    if(ln[num].k*tree[pos].r+ln[num].b>=ln[tree[pos].bst].k*tree[pos].r+ln[tree[pos].bst].b) upd(pos*2+1,num);
}
int ask(int pos,int kk){
    if(tree[pos].r<kk||kk<tree[pos].l) return -INF;
    if(tree[pos].l==tree[pos].r) return ln[tree[pos].bst].k*kk+ln[tree[pos].bst].b;
    return max(max(ask(pos*2,kk),ask(pos*2+1,kk)),ln[tree[pos].bst].k*kk+ln[tree[pos].bst].b);
}
int t[N],c[N],f[N];
int n,cnt,maxn=-INF,ans=-INF;
signed main(){
    ios::sync_with_stdio(false);
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>t[i];
        maxn=max(maxn,t[i]);
    }
    for(int i=1;i<=n;i++){
        cin>>c[i];
    }
    ln[0]={0,-INF};
    build(1,1,maxn);
    f[1]=0;
    ln[++cnt]={t[1],f[1]/2-c[1]};
    upd(1,cnt);
    for(int i=2;i<=n;i++){
        f[i]=ask(1,t[i]);
        ln[++cnt]={t[i],f[i]/2-c[i]};
        upd(1,cnt);
    }
    for(int i=1;i<=n;i++){
        ans=max(ans,f[i]);
    }
    cout<<ans;
    return 0;
}

本代码可以通过洛谷评测。

Written by toolong114514 on 2024.5.30.