题解：P11876 [威海市赛2024] 收徒！

· · 题解

思维 + 问题转化 + 结合贪心思想的二分优化求最长不下降子序列 + 记录方案

在一张巨大的网格上，只能向右和向下移动，要求从起始位置移动到终点时最多能途径的物品数，考虑到一步关键转化 trick：将这些物品按照 x 为第一关键字升序排序，y 为第二关键字升序排序，那么途径能获得的最多物品数就是对这物品的 y 坐标求最长不下降子序列。并且注意本题只能通过结合贪心思想的二分优化求最长不下降子序列，而不能使用树状数组，因为本题需要记录路径，树状数组只能求长度而无法记录。

由于要记录路径，于是考虑定义 pre_i 记录当前的排序处理后的第 i 件物品作为最长不下降子序列的结尾时前一件物品的下标，便于递推输出方案，然后用 cur\_idx_i 记录当前的长度为 i 的最长不下降子序列的下标。

相比 结合贪心思想的二分优化求最长上升子序列，本题是求最长不下降子序列，故你需要考虑将 a_i 接在先前 f 中 \le a_i 的最后一个位置之后，即 \gt a_i 的第一个位置。

因为 f_i 表示长度为 i 的最小结尾，显然你不应该考虑其后继，只应该考虑其前驱。

#define rep(x,y,z) for(int x=y;x<=z;x++)
const int N=2e5+5;
int h,w,n;
struct node{
    int x,y;
    bool operator<(node &t){
        if(x==t.x) return y<t.y;
        return x<t.x;
    }
}p[N],ans[N<<1];
int f[N<<1];
int pre[N<<1],cur_idx[N<<1];
int cnt;
void dfs(int i){
    if(!i) return;
    dfs(pre[i]);
    ans[++cnt]={p[i].x,p[i].y};
}
void solve(){
    cin>>h>>w>>n;
    rep(i,1,n) cin>>p[i].x>>p[i].y;
    sort(p+1,p+1+n);
    int len=1;
    f[len]=p[1].y;
    cur_idx[len]=1,pre[len]=0;
    rep(i,2,n){
        if(p[i].y>=f[len]){
            pre[i]=cur_idx[len];
            f[++len]=p[i].y;
            cur_idx[len]=i;
        }
        else{
            int j=upper_bound(f+1,f+1+len,p[i].y)-f;
            f[j]=p[i].y;
            cur_idx[j]=i;
            pre[i]=cur_idx[j-1];
        }
    }
    cout<<len<<endl;
    ans[1]={1,1};
    cnt=1;
    dfs(cur_idx[len]);
    ans[++cnt]={h,w};
    rep(i,2,cnt){
        int stepx=ans[i].x-ans[i-1].x;
        int stepy=ans[i].y-ans[i-1].y;
        while(stepx--) cout<<"D";
        while(stepy--) cout<<"R";
    }
}