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

· · 题解

题目大意

有 n 个岛，每个岛有两个权值 F_i，T_i。设价值为 x，则在离开一座岛屿时，x 会变为 \frac{x}{2}-F_i。从一座岛屿 i 到达岛屿 j 时，x 会增加 T_iT_j。你初始在 1 号节点，每次只能前往编号更大的节点，求最大的 x。

题目分析

设 dp_i 表示在岛屿 i 停留时的最大价值，则 dp_i=\max\limits_{j<i}(\frac{dp_j}{2}-F_j+T_iT_j)，显然括号里的式子中，把和 j 有关的量当成常数，则式子为一次函数，李超线段树维护即可，复杂度 O(n\log V)。

这题咋没数据啊，我先挂着我的代码等有数据了再来检查。

update 2024/4/18：修改了数组大小，能够通过民间数据。

#include<bits/stdc++.h>
#define int long long
#define R 1,1,20000
#define mid (l+r>>1)
#define lc x<<1,l,mid
#define rc x<<1|1,mid+1,r
#define rep(x,y,z) for(int x=(y);x<=(z);x++)
#define repn(x) rep(x,1,n)
inline int read(){int s=0,w=1;char c=getchar();while(c<48||c>57) {if(c=='-') w=-1;c=getchar();}while(c>=48&&c<=57)s=(s<<1)+(s<<3)+c-48,c=getchar();return s*w;}
const int N =5e5+5,llf=1e18;
using namespace std;
int n=read(),a[N],f[N],dp[N],tot,xd[N<<2],ans;
struct segment{
    int k,b;
}d[N];
int get(int x,int id){
    if(!id)return -llf;
    return d[id].k*x+d[id].b;
}
void pushdown(int x,int l,int r,int id){
    if(!xd[x])xd[x]=id;
    if(get(mid,id)>get(mid,xd[x]))swap(xd[x],id);
    if(get(l,id)>get(l,xd[x]))pushdown(lc,id);
    if(get(r,id)>get(r,xd[x]))pushdown(rc,id);
}
int query(int x,int l,int r,int p){
    if(l==r)return get(p,xd[x]);
    return max(get(p,xd[x]),p<=mid?query(lc,p):query(rc,p));
}
signed main(){
    repn(i)a[i]=read();
    repn(i)f[i]=read();
    d[++tot]={a[1],-f[1]},pushdown(R,tot);
    rep(i,2,n)dp[i]=query(R,a[i]),d[++tot]={a[i],dp[i]/2-f[i]},pushdown(R,tot),ans=max(ans,dp[i]);
    cout <<ans;
    return 0;
}