题解：AT_abc369_f [ABC369F] Gather Coins

zibenlun · 2024-09-02 08:44:57 · 题解

思路

每一个硬币一定是从比它横纵坐标都小的硬币上转移过来，我们将所有硬币先按横坐标排序，再按纵坐标排序，枚举每一个硬币，用树状数组维护，并标记每一个硬币从哪一个硬币转移过来。

代码

#include<bits/stdc++.h>
#define int long long
#define lowbit(x) (x&(-x))
#define faster ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
using namespace std;
int n,m,q;
int c[200005];
int ans;
struct nd{
    int x,y;
}a[200005];
int dp[200005];
int v[200005];
int pos[200005];
bool cmp(nd x,nd y){
    if(x.x==y.x) return x.y<y.y;
    return x.x<y.x;
}
void add(int x,int e,int id){
    for(int i=x;i<=m;i+=lowbit(i)){
        if(e>=c[i]) c[i]=e,pos[i]=id;
    }
}
int ask(int x){
    int sum=0,ps=0;
    for(int i=x;i;i-=lowbit(i)){
        if(c[i]>=sum){
            sum=c[i];
            ps=pos[i];
        }
    }
    return ps;
}
signed main() {
    faster
    cin>>n>>m>>q;
    for(int i=1;i<=q;i++){
        cin>>a[i].x>>a[i].y;
    }
    sort(a+1,a+1+q,cmp);
    a[0].x=1;
    a[0].y=1;
    a[q+1].x=n;
    a[q+1].y=m;
    for(int i=1;i<=q;i++){
        int x=ask(a[i].y);
        dp[i]=dp[x]+1;
        v[i]=x;
        add(a[i].y,dp[i],i);
    }
    int k=ask(m);
    // cout<<x;
    cout<<dp[k];
    cout<<"\n";
    int x=1,y=1;
    stack<int> s;
    s.push(q+1);
    int pos=k;
    while(pos!=0){
        s.push(pos);
        pos=v[pos];
    }
    while(s.size()){
        int i=s.top();
        s.pop();
        while(x<a[i].x) {
            cout<<"D";
            x++;
        }
        while(y<a[i].y){
            cout<<"R";
            y++;
        }
    }
    return 0;
}