萌新刚学OI,0pts请求DEBUG
  • 板块CF10D LCIS
  • 楼主Hisy
  • 当前回复3
  • 已保存回复3
  • 发布时间2024/7/29 14:12
  • 上次更新2024/7/29 14:55:15
查看原帖
萌新刚学OI,0pts请求DEBUG
922691
Hisy楼主2024/7/29 14:12
#include<bits/stdc++.h>
#define MAXN 505
using namespace std;
int a[MAXN],b[MAXN],dp[MAXN][MAXN],lst[MAXN][MAXN],len[MAXN];
int main(){
	ios::sync_with_stdio(false);
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;++i){
		cin>>a[i];
	}
	for(int i=1;i<=m;++i){
		cin>>b[i];
	}
	for(int i=1;i<=n;++i){
		for(int j=1;j<=m;++j){
			if(a[i]!=b[j]){
				dp[i][j]=dp[i-1][j];
			}else{
				dp[i][j]=1;
				len[j]=1;
				for(int k=0;k<j;++k){
					if(b[k]<b[j]&&dp[i-1][k]>=dp[i][j]){
						dp[i][j]=dp[i-1][k]+1;
						len[j]=len[k]+1;
						for(int l=1;l<=len[j];++l){
							lst[j][l]=lst[k][l];
						}
					}
				}
				lst[j][len[j]]=b[j];
			}
		}
	}
	pair<int,int> ans=make_pair(len[1],1);
	for(int i=2;i<=m;++i){
		ans=max(ans,make_pair(len[i],i));
	}
	cout<<ans.first<<endl;
	for(int i=1;i<=len[ans.second];++i){
		cout<<lst[ans.second][i]<<" ";
	}
	return 0;
}
2024/7/29 14:12
加载中...