abc266 Ex - Snuke Panic (2D)

树状数组优化 dp ，带权最长链

---

大体和官方题解差不多，只做个记录。

题意

二维坐标系上有 $n$ 个关键点，你初始在 $(0, 0)$ 位置，初始时刻为 $0$ ，你若在 $t_i$ 时刻走到点 $(x_i, y_i)$ 则会获得 $a_i$ 的价值，最大化你能获得的价值。
其中你每一时刻可以进行下列两种操作之一：

• 保持 $x$ 坐标不变，或者将其变为 $x - 1$ 或 $x + 1$ 。
• 保持 $y$ 坐标不变，或者将其变为 $y + 1$ 。

其中 $1 \leq n \leq 10^5, 1 \leq t_i \leq 10^9, 0 \leq x_i, y_i \leq 10^9, 1 \leq a_i \leq 10^9$ 。

思路

考虑朴素的 $dp$ ，记 $dp[t][x][y]$ 表示 $t$ 时刻走到点 $(x, y)$ 能获得的最大价值，则转移方程显然：

$$\begin{cases} dp[t][x][y] = \max(dp[t'][x'][y']) + val[x][y]\\ t - t' \geq |x - x'| + y - y'\\ y \geq y'\\ \end{cases}$$

转移合法的条件比较复杂，考虑对其进行转换以方便优化。

$$t - t' \geq |x - x'| + y - y'\\ \iff \begin{cases} t - t' \geq x - x' + y - y'\\ t - t' \geq - x + x' + y - y'\\ \end{cases}\\ \iff \begin{cases} t - x - y \geq t' - x' - y'\\ t + x - y \geq t' + x' - y'\\ \end{cases}$$

记 $a = t - x - y, b = t + x - y$ ，并将原 $dp$ 数组转变为 $dp[y][a][b]$ ， $y, a, b$ 的意义如上。
则有转移方程：

$$\begin{cases} dp[y][a][b] = \max(dp[y'][a'][b']) + val[x][y]\\ y \geq y'\\ a \geq a'\\ b \geq b'\\ \end{cases}$$

显然转移等价于求一个三维偏序带权最长链，并且我们只需要记录 $n$ 个关键点对应的状态，对 $y$ 排序后套二维树状数组 / 线段树优化 $dp$ 或者套 $cdq$ 分治即可，注意删去初始不能从 $(0, 0)$ 到达的点，这部分点不能当作起点被计算。
总复杂度为 $O(n \cdot log^2n)$ 。

代码

树状数组套线段树

/*
    Author: Cupids_Bow
    Time: 2022-08-27 20:49:14
*/
#include<bits/stdc++.h>
using namespace std;

using i64=long long;

constexpr int N=1e5+5;

int n;
vector<array<int,4>> arr;
vector<int> X,Y;
i64 ans;
struct tree{
    int tot;
    int rt[N];
    int lc[N<<7];
    int rc[N<<7];
    i64 maxn[N<<7];
    void add(int &x,int l,int r,int pos,i64 val){
        if(!x) x=++tot;
        if(l==r){
            maxn[x]=max(maxn[x],val);
            return;
        }
        int mid=l+r>>1;
        if(pos<=mid) add(lc[x],l,mid,pos,val);
        else add(rc[x],mid+1,r,pos,val);
        maxn[x]=max(maxn[lc[x]],maxn[rc[x]]);
        return;
    }
    i64 search(int x,int l,int r,int ql,int qr){
        if(!x||ql>qr) return 0;
        if(l>=ql&&r<=qr) return maxn[x];
        int mid=l+r>>1;
        i64 res=0;
        if(mid>=ql) res=max(res,search(lc[x],l,mid,ql,qr));
        if(mid+1<=qr) res=max(res,search(rc[x],mid+1,r,ql,qr));
        return res;
    }
}tr;
struct BIT2D{
    int n,m;
    BIT2D(){}
    BIT2D(int _n,int _m){
        n=_n;
        m=_m;
    }
    void add(int x,int y,i64 k){
        for(int i=x;i<=n;i+=(i&-i)) tr.add(tr.rt[i],1,m,y,k);
    }
    i64 search(int x,int y){
        if(x==0||y==0) return 0;
        i64 res=0;
        for(int i=x;i;i-=(i&-i)) res=max(res,tr.search(tr.rt[i],1,m,1,y));
        return res;
    }
}bit2d;

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);

    cin>>n;
    for(int i=1,t,x,y,a;i<=n;i++){
        cin>>t>>x>>y>>a;
        if(t-x-y<0||t+x-y<0) continue;
        arr.push_back({y,t-x-y,t+x-y,a});
        X.push_back(t-x-y);
        Y.push_back(t+x-y);
    }
    sort(arr.begin(),arr.end());
    X.push_back(0);
    sort(X.begin(),X.end());
    X.erase(unique(X.begin(),X.end()),X.end());
    Y.push_back(0);
    sort(Y.begin(),Y.end());
    Y.erase(unique(Y.begin(),Y.end()),Y.end());
    bit2d=BIT2D(X.size(),Y.size());
    for(auto [y,a,b,val]:arr){
        a=lower_bound(X.begin(),X.end(),a)-X.begin()+1;
        b=lower_bound(Y.begin(),Y.end(),b)-Y.begin()+1;
        i64 res=bit2d.search(a,b);
        ans=max(ans,res+val);
        bit2d.add(a,b,res+val);
    }
    cout<<ans;

    return true&&false;
}