[ABC353G] Merchant Takahashi

· · 题解

题目

考察：树状数组，线段树，动态规划。
题意简述：
有 n+1 个城市，编号为 [0,n]，你接到了 m 个关于一个活动的消息：t_i,p_i。

你一开始在 $0$ 号城市，每个活动你可以参加，也可以不参加，但必须按顺序参加，求获得的钱数的最大值。 数据范围： - $1\le n,m\le 2\times 10^5

我们可以看出明显是一道 dp 题，然后 f_i 肯定跟 f_j\ \ (0\le j<i) 有关，很容易推出状态转移方程：

f_i=\max_{j=0}^{i-1}(f_j-c\times|x_i-x_j|+p_i)

但是这样转移是 O(m^2) 的，无法通过 m\le 2\times 10^5 的数据，考虑优化。

每个点造成的贡献是 f_j-c\times|x_i-x_j|+p_i，其中 p_i 是固定的，那么在 f_j-c\times|x_i-x_j| 中，我们考虑如何拆掉绝对值符号，我们分类讨论 |x_i-x_j|：

那么我们可以用树状数组或线段树维护 f_{x_j}\ (x_j\le x_i) 的前缀最大值，f_{x_j}\ (x_j>x_i) 的后缀最大值（由于树状数组只能维护前缀最大值，所以我们将 f_{x_j} 变为 f_{n-x_j}）
我们定义两个树状数组，f 是维护 x_j\le x_i 的最大值，查询的结果是 fmax，g 是维护 x_j>x_i 的最大值，查询的结果是 gmax，那么 f_i 就等于：

f_i=\max(fmax+c\times x_i,gmax-c\times x_i)+p_i

然后我们在修改 f,g 中的值即可。

这样我们就可以在 O(m\log_2n) 的复杂度内完成本题。

代码： 

#include<bits/stdc++.h>
#define int long long
#define inl inline
#define rep(i,x,y) for(int i=x;i<=y;++i)
#define per(i,x,y) for(int i=x;i>=y;--i)
#define fst; ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl '\n'
#define fi first
#define se second
#define INF LLONG_MAX
using namespace std;
const int N=2e5+5;
int n,c,m,t,p,num,ans; 
struct BIT{
    int a[N];
    inl BIT(){
        memset(a,-0x3f,sizeof(a));
    }
    inl int lowbit(int x){
        return x&(-x);
    }
    inl void add(int x,int k){
        while(x<=n){
            a[x]=max(a[x],k);
            x+=lowbit(x);
        }
        return;
    }
    inl int getmax(int x){
        int mx=-INF;
        while(x){
            mx=max(mx,a[x]);
            x-=lowbit(x);
        }
        return mx;
    }
}t1,t2;
signed main(){
    fst; 
    cin>>n>>c>>m;
    t1.add(1,c);
    t2.add(n,-c);
    rep(i,1,m){
        cin>>t>>p;
        num=max(t1.getmax(t)-c*t,t2.getmax(n-t)+c*t)+p;
        ans=max(ans,num);
        t1.add(t,num+c*t);
        t2.add(n-t+1,num-c*t);
    }
    cout<<ans;
    return 0;
}