WA on#7 求 hack
  • 板块CF10D LCIS
  • 楼主light_searcher
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/10/1 22:03
  • 上次更新2024/10/2 09:53:26
查看原帖
WA on#7 求 hack
724648
light_searcher楼主2024/10/1 22:03
#include<bits/stdc++.h>
using namespace std;
const int N=3e3+5;
int n,m,a[N],b[N],f[N][N],x,y,g[N][N];
void print(int x,int y){
	if(!x) return;
	if(a[x]!=b[y]) print(x-1,y);
	else{
		print(x-1,g[x][y]);
		printf("%d ",b[y]);
	}
}
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	scanf("%d",&m);
	for(int i=1;i<=m;i++) scanf("%d",&b[i]);
	for(int i=1;i<=n;i++){
		int id=0;
		for(int j=1;j<=m;j++){
			if(a[i]!=b[j]) f[i][j]=f[i-1][j];
			else f[i][j]=f[i-1][id]+1;
			g[i][j]=id;
			if(b[j]<a[i]&&f[i-1][j]>f[i-1][id]) id=j;
			if(f[i][j]>f[x][y]){
				x=i;
				y=j;
			}
		}
	}
	printf("%d\n",f[x][y]);
	print(x,y);
	return 0;
}
2024/10/1 22:03
加载中...