题解：P11876 收徒！

· · 题解

题目描述

给 定一个 h\times w 的棋盘，以及 N 个棋子，从棋盘左上角出发，每次向下或向右移动一个单位，求到达右下角时可以经过的最多棋子数。

思路分析

1.暴力思路

构建一个数组容器，每次弹出一个并压入向下和向右俩个方向。明显不行。

2.棋盘 dp 思路

思路类似于经典入门动态规划题目过河卒但是问题在于本题棋盘大小为 2\times10^5，因此不仅时间不通过，空间也会爆。

3.棋子 dp 思路

观察题目，我们发现棋子的数量为 2\times10^5，因此我们不难想到可以从记录棋盘状态转变为记录棋子的状态。

重点：我们可以发现对于任意的棋子，他都是由他左上方的棋子或者是 (1,1) 走过来的。而这个来源的棋子是从 (1,1) 走到左上方所有棋子中的最大值的那个棋子。

举例：我们缩小棋子数量，有一个 2\times3 的棋盘，只有俩个棋子为 (1,2) 和 (2,3)，且第一个棋子在第二个棋子的左上方，那么到达第二个棋子的时候必定经过第一个棋子。

因此，具体思路为开一个 f 数组，f_i 中所储存的棋子表示为从 (1,1) 到此棋子的最大值为 i。例如上面，(1,2) 存在 f_1 中，(2,3) 存在 f_2 中。遍历所有棋子，用变量 ma 记录目前遍历过的棋子的最大的值，令 dq 变量为 ma 开始遍历，若发现其中储存的棋子是在当前棋子的左上角的（即可以通过该棋子到达当前遍历的棋子）视为找到了，存入 f_{dq+1}，并且跳出循环，修改 ma 为 \max(ma,dq+1)，若 f_{dq} 遍历完了没找到则 dq 减 1。若 dq 到 0 了则直接存入 f_1，同时更新 ma，同时开一个 ly 表示来源的数组记录每个棋子是从那个棋子过来的，每次存入 f 数组之后对 ly 数组进行更新操作。最后依据 ly 数组进行回溯即可。

时间复杂度最大为 O(n^2) 空间问题解决了，但是依旧超时。

4.棋子 dp 及二分思路（AC 思路）

我们发现对于每个棋子，若找了的可以从左上角来的棋子，若记从 (1,1) 到来的棋子的最大值为 k，那么对于 f_{i<k} 的数组中，肯定会有若干个棋子可以走到当前遍历的棋子。因此，我们令 l 为 1，r 为 ma。若 f_{mid} 中存在可以走来的棋子修改 l，不存在则修改 r。记录可行的最大的 mid，初始为 0。压入 f 并更新 ma 和 ly 数组。时间复杂度为 O(n\times \log_n)。

代码如下

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;

vector<int>m[N];

struct node{
    int xx;
    int yy;
}f[N];

bool cmp(node a,node b){
    if(a.xx==b.xx){
        return a.yy<b.yy;
    }else{
        return a.xx<b.xx;
    }
}
int ly[N];

int main(){
    int h,w,n;
    cin>>h>>w>>n;
    for(int i=1;i<=n;i++){
        scanf("%d%d",&f[i].xx,&f[i].yy);
    }
    sort(f,f+n+1,cmp);//不能不要 
    int ma=0;
    for(int i=1;i<=n;i++){
        int l=1,r=ma;
        int dqll=0;
        int dq=0;
        while(l<=r){
            int mid=l+r>>1;
            int flag=0;
            int ll;
            for(int k:m[mid]){
                if(f[k].yy<=f[i].yy){
                    flag=1;
                    ll=k;
                    break;
                }
            }
            if(flag){
                if(mid>dq){
                    dq=mid;
                    dqll=ll;
                }
                l=mid+1;
            }else{
                r=mid-1;
            }
        }

        ma=max(ma,dq+1);
        ly[i]=dqll;
        m[dq+1].push_back(i);
    }

    int ans=m[ma][0];
    string s="";
    int prow=ans;
    int dqi=h;
    int dqj=w;
    while(1){
        int proi=f[prow].xx;
        int proj=f[prow].yy;
        if(prow==0){
            proi=1;
            proj=1;
        }
        string dqs="";
        for(int i=proi;i<dqi;i++){
            dqs+='D';
        }
        for(int i=proj;i<dqj;i++){
            dqs+='R';
        }
        s=dqs+s;
        dqi=proi;
        dqj=proj;
        if(prow==0)break;

        prow=ly[prow];

    }
    cout<<ma<<endl;
    cout<<s<<endl;
}

/*
0 0 1 1 1 
0 0 0 0 1
0 0 0 1 0
0 0 0 1 0
0 0 0 1 0

5 5 7
1 3
1 4
1 5
2 5
3 4
4 4
5 4

*/

蒟蒻第一次写题解，写的不好还请见谅，欢迎大家提问及纠错，最后求审核大大通过。