题解：P11876 [威海市赛2024] 收徒！

思维 + 问题转化 + 结合贪心思想的二分优化求最长不下降子序列 + 记录方案

在一张巨大的网格上，只能向右和向下移动，要求从起始位置移动到终点时最多能途径的物品数，考虑到一步关键转化 trick：将这些物品按照

x

为第一关键字升序排序，

y

为第二关键字升序排序，那么途径能获得的最多物品数就是对这物品的

y

坐标求最长不下降子序列。并且注意本题只能通过结合贪心思想的二分优化求最长不下降子序列，而不能使用树状数组，因为本题需要记录路径，树状数组只能求长度而无法记录。

由于要记录路径，于是考虑定义

pre_i

记录当前的排序处理后的第

i

件物品作为最长不下降子序列的结尾时前一件物品的下标，便于递推输出方案，然后用

cur\_idx_i

记录当前的长度为

i

的最长不下降子序列的下标。

相比结合贪心思想的二分优化求最长上升子序列，本题是求最长不下降子序列，故你需要考虑将

a_i

接在先前

f

中

\le a_i

的最后一个位置之后，即

\gt a_i

的第一个位置。

因为

f_i

表示长度为

i

的最小结尾，显然你不应该考虑其后继，只应该考虑其前驱。

CPP

#define rep(x,y,z) for(int x=y;x<=z;x++)
const int N=2e5+5;
int h,w,n;
struct node{
	int x,y;
	bool operator<(node &t){
		if(x==t.x) return y<t.y;
		return x<t.x;
	}
}p[N],ans[N<<1];
int f[N<<1];
int pre[N<<1],cur_idx[N<<1];
int cnt;
void dfs(int i){
	if(!i) return;
	dfs(pre[i]);
	ans[++cnt]={p[i].x,p[i].y};
}
void solve(){
	cin>>h>>w>>n;
	rep(i,1,n) cin>>p[i].x>>p[i].y;
	sort(p+1,p+1+n);
	int len=1;
	f[len]=p[1].y;
	cur_idx[len]=1,pre[len]=0;
	rep(i,2,n){
		if(p[i].y>=f[len]){
			pre[i]=cur_idx[len];
			f[++len]=p[i].y;
			cur_idx[len]=i;
		}
		else{
			int j=upper_bound(f+1,f+1+len,p[i].y)-f;
			f[j]=p[i].y;
			cur_idx[j]=i;
			pre[i]=cur_idx[j-1];
		}
	}
	cout<<len<<endl;
	ans[1]={1,1};
	cnt=1;
	dfs(cur_idx[len]);
	ans[++cnt]={h,w};
	rep(i,2,cnt){
		int stepx=ans[i].x-ans[i-1].x;
		int stepy=ans[i].y-ans[i-1].y;
		while(stepx--) cout<<"D";
		while(stepy--) cout<<"R";
	}
}

题解：P11876 [威海市赛2024] 收徒！

文章操作

思维 + 问题转化 + 结合贪心思想的二分优化求最长不下降子序列 + 记录方案

相关推荐

评论

题解：P11876 [威海市赛2024] 收徒！