2 条题解
-
0
#include<bits/stdc++.h> using namespace std; const int N=2e5+10; struct node{int x,y;}a[N]; bool cmp(node n1,node n2){return n1.x!=n2.x?n1.x<n2.x:n1.y<n2.y;} int c[N],id[N],dp[N],pre[N],n,m; void add(int x,int k,int tid) { for(;x<=m;x+=x&-x) if(k>=c[x]) id[x]=tid,c[x]=k; } void dfs(int x,int px,int py) { if(pre[x])dfs(pre[x],a[x].x,a[x].y); for(int i=a[x].x+1;i<=px;i++)cout<<"D"; for(int i=a[x].y+1;i<=py;i++)cout<<"R"; } signed main() { int k;cin>>n>>m>>k; for(int i=1;i<=k;i++)cin>>a[i].x>>a[i].y; a[++k]={n,m};a[++k]={1,1}; sort(a+1,a+k+1,cmp); for(int i=1;i<=k;i++) { int t=a[i].y; for(;t;t-=t&-t) if(c[t]>=dp[i]) dp[i]=c[t],pre[i]=id[t]; dp[i]++; add(a[i].y,dp[i],i); } cout<<dp[k]-2<<'\n'; dfs(pre[k],n,m); return 0; } -
0
#include<bits/stdc++.h> #define int long long #define lowbit(x) (x&(-x)) using namespace std; const int N=2e5+10; int n,m,q,c[N],ans; struct node{ int x,y; void read(){scanf("%lld%lld",&x,&y);} }a[N]; int dp[N],v[N],pos[N]; bool cmp(node x,node 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(){ scanf("%lld%lld%lld",&n,&m,&q); for(int i=1;i<=q;i++)a[i].read(); 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);printf("%lld\n",dp[k]); 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){ printf("D"); x++; } while(y<a[i].y){ printf("R"); y++; } } return 0; }
- 1
信息
- ID
- 7969
- 时间
- 2000ms
- 内存
- 1024MiB
- 难度
- 8
- 标签
- 递交数
- 15
- 已通过
- 6
- 上传者