自动搬运

查看原文

来自洛谷，原作者为

	FallingFYC_ 但我仍然渴望在每一次追忆之旅中留下闲暇时间，在一个场景前驻足，在岁月的朦胧里瞭望过去的自己，感受尽可能多的甜蜜。

搬运于2025-08-24 23:06:32，当前版本为作者最后更新于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;
}