题解：P11335 [NOISG 2020 Finals] Arcade

FallingFYC_ · 2025-06-25 11:22:45 · 题解

P11335 [NOISG 2020 Finals] Arcade

如果一只手能在 T_i 时按到按钮 A_i 且在 T_j 时按到按钮 A_j（T_i<T_j），则必须满足 T_j-T_i \ge |A_i-A_j|。拆一下绝对值得：\begin{cases} T_j-T_i \ge A_j - A_i \\ T_j-T_i \ge A_i - A_j \end{cases} 移项得：\begin{cases} T_j-A_j \ge T_i-A_i \\ T_j+A_j \ge T_i+A_i \end{cases}。

不妨把每组 T_i 和 A_i，看作一个二元组：(T_i+A_i,T_i-A_i)，这样问题就转化为了最小链覆盖，运用 Dilworth 定理，即求出最长反链长度。可以先将第一维升序排序，求出第二维最长下降子序列即可。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
#define REV(i,a,b) for(int i=(a);i>=(b);i--)
#define CLOSE_TIE ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define psbk push_back
#define mkp make_pair
#define endl '\n'
#define outval(x) cout<<(#x)<<'='<<x<<endl;
#define outarr(a,len) {\
    cout<<(#a)<<'=';\
    FOR(i,1,len)cout<<a[i]<<' ';\
    cout<<endl;\
}
ll read(){
    char c=getchar();
    ll f=1,res=0;
    while(c<'0'||c>'9'){
        if(c=='-')f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        res=res*10+c-'0';
        c=getchar();
    }
    return res*f;
}
const int N=5e5+5;
struct Node{
    int x,y;
}p[N];
int n,m,t[N],a[N],f[N],ans;
signed main(){
    n=read();m=read();
    FOR(i,1,m){
        t[i]=read();
    }
    FOR(i,1,m){
        a[i]=read();
    }

    FOR(i,1,m){
        p[i]={t[i]+a[i],t[i]-a[i]};
    }
    sort(p+1,p+m+1,[&](Node a,Node b){return a.x==b.x?a.y<b.y:a.x<b.x;});
    memset(f,0x3f,sizeof f);
    f[0]=0;
    reverse(p+1,p+m+1);
    FOR(i,1,m){
        int t=lower_bound(f+1,f+m+1,p[i].y)-f;
        f[t]=p[i].y;
        ans=max(ans,t);
    }
    cout<<ans;
    return 0;
}