求条玄关
  • 板块学术版
  • 楼主RAY091016
  • 当前回复0
  • 已保存回复0
  • 发布时间2025/7/1 19:14
  • 上次更新2025/7/1 20:26:02
查看原帖
求条玄关
772875
RAY091016楼主2025/7/1 19:14

死循环,求条

题目概述:从一个给定序列中不断删去其最长上升子序列并记录每次删除元素及删除次数

#include<bits/stdc++.h>
using namespace std;
int n,a[64040],lst[64040],nxt[64040],f[64040],pre[64040],maxn[64040],vis[64040],maxi,tot=1,head,tail;
stack<int>st[550];
int main(){
	cin>>n;
	head=1,tail=n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		nxt[i]=i+1;
		lst[i]=i-1;
	}
	while(n){
		maxn[tot]=1;
		for(int i=head;i<=tail;i=nxt[i]){
			f[i]=1;
			pre[i]=i;
		}
		for(int i=head;i<=n;i=nxt[i]){
			for(int j=head;j<i;j=nxt[j]){
				if(a[j]<a[i]){
					if(f[j]+1>f[i]){
						f[i]=f[j]+1;
						pre[i]=j;
					}
				}
			}
		}
		for(int i=head;i<=tail;i=nxt[i]){
			if(f[i]>maxn[tot]){
				maxn[tot]=f[i];
				maxi=i;
			}
		}
		while(pre[maxi]!=maxi){
			st[tot].push(a[maxi]);
			vis[maxi]=1;
			if(lst[maxi]!=0){
				nxt[lst[maxi]]=nxt[maxi];
			}
			if(nxt[maxi]!=n+1){
				lst[nxt[maxi]]=lst[maxi];
			}
			maxi=pre[maxi];
		}
		st[tot].push(a[maxi]);
		vis[maxi]=1;
		if(lst[maxi]!=0){
			nxt[lst[maxi]]=nxt[maxi];
		}
		if(nxt[maxi]!=n+1){
			lst[nxt[maxi]]=lst[maxi];
		}
		tot++;
		if(vis[head]=1){
			for(int i=head+1;i<=tail;i=nxt[i]){
				if(!vis[i]){
					head=i;
					break;
				}
			}
		}
		if(vis[tail]=1){
			for(int i=tail-1;i>=head;i=lst[i]){
				if(!vis[i]){
					tail=i;
					break;
				}
			}
		}
		n-=maxn[tot];
	}
	tot--;
	cout<<tot<<endl;
	for(int i=1;i<=tot;i++){
		cout<<maxn[i]<<" ";
		while(!st[i].empty()){
			cout<<st[i].top()<<" ";
			st[i].pop();
		}
		cout<<endl;
	}
	return 0;
}

2025/7/1 19:14
加载中...