本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 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;
}