里面大概有一两个星期吧，挑一些有价值的写。
[ABC369F] Gather Coins
来补的题目。
先考虑不输出方案的写法。排序过后可以用一个 DP 实现。
注意到 DP 的转移方程只和 max 有关，所以可以用数据结构优化。
排序过后保证横坐标不降，所以只需要对纵坐标开一个树状数组，维护最大值，能做到 \(\mathcal{O}(k\log n)\) 的转移。
现在要求输出方案，我们可以记录每一个 DP 数组中的元素从哪里转移过来，最后倒序查找输出。
这样的话我们同事需要对树状数组多维护点东西。除了基本的记录 max 数组，我们再开一个记录编号的数组，记录树状数组中每一个值对应的编号。
这样转移的时候更新最大值时可以同时更新编号数组，实现维护。
点击查看代码
#include <bits/stdc++.h>
// #define int long long
using namespace std;
inline int read()
{
int w=1,s=0;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')w=-1;ch=getchar();}
while(isdigit(ch)){s=s*10+(ch-'0');ch=getchar();}
return w*s;
}
const int maxn=5e5+10;
const int mod=998244353;
const int inf=1e9+7;
int n,m,k;
struct no
{
int x,y;
}a[maxn];
int dp[maxn],pre[maxn];
int c[maxn<<1],d[maxn<<1];
int lb(int x){return x&-x;}
void add(int x,int y,int id){for(;x<=maxn;x+=lb(x)){if(c[x]<y)c[x]=y,d[x]=id;}}
no ask(int x){int ans=0,id=0;for(;x;x-=lb(x)){if(c[x]>ans){ans=c[x];id=d[x];}}return {ans,id};}
vector<char> v;
void work(no s,no t)
{
for(int i=1;i<=abs(s.x-t.x);i++)v.push_back('D');
for(int i=1;i<=abs(s.y-t.y);i++)v.push_back('R');
}
signed main()
{
#ifdef Lydic
freopen(".in","r",stdin);
freopen(".out","w",stdout);
// #else
// freopen("Stone.in","r",stdin);
// freopen("Stone.out","w",stdout);
#endif
cin>>n>>m>>k;
for(int i=1;i<=k;i++)a[i]={read(),read()};
sort(a+1,a+k+1,[](no x,no y){return x.x<y.x||x.x==y.x&&x.y<y.y;});
for(int i=1;i<=k;i++)dp[i]=1;
add(a[1].y,1,1);
for(int i=2;i<=k;i++)
{
no now=ask(a[i].y);
dp[i]=now.x+1;
pre[i]=now.y;
add(a[i].y,dp[i],i);
// cout<<i<<' '<<pre[i]<<endl;
}
int ans=0,id=0;
for(int i=1;i<=k;i++)
{
if(dp[i]>ans)
{
ans=dp[i];
id=i;
}
}
cout<<ans<<endl;
// cout<<id<<endl;
// cout<<a[id].x<<' '<<a[id].y<<endl;
work(no{n,m},a[id]);
// for(auto i : v)cout<<i;puts("");
while(1)
{
if(!pre[id]){work(no{1,1},a[id]);break;}
work(a[id],a[pre[id]]);
id=pre[id];
}
reverse(v.begin(),v.end());
for(auto i : v)cout<<i;puts("");
return 0;
}