MnZn求助,一道简单题
  • 板块CF10D LCIS
  • 楼主WindZR
  • 当前回复0
  • 已保存回复0
  • 发布时间2021/11/19 21:42
  • 上次更新2023/11/4 00:05:29
查看原帖
MnZn求助,一道简单题
233025
WindZR楼主2021/11/19 21:42

就是最后输出方案的时候,使用被注释掉的那个forfor循环就会出错,使用下面的就没有问题,求助。

#include<bits/stdc++.h>
#define re int
#define ii inline int
#define iv inline void
using namespace std;
const int N=510;
int n,m,ans,pos;
int a[N],b[N];
int f[N][N],pre[N][N];
stack<int> sta;
ii read()
{
	int x=0; char ch=getchar(); bool f=1;
	while(ch<'0' or ch>'9')
	{
		if(ch=='-') f=0;
		ch=getchar();
	}
	while(ch>='0' and ch<='9')
	{
		x=(x<<1)+(x<<3)+(ch^48);
		ch=getchar();
	}
	return f?x:(-x);
}
iv out(int x)
{
	if(!x) return;
	out(pre[n][x]);
	printf("%d ",b[x]);
}
signed main()
{
	n=read();
	for(re i=1;i<=n;i++) a[i]=read();
	m=read();
	for(re i=1;i<=m;i++) b[i]=read();
	for(re i=1;i<=n;i++)
	{
		for(re j=1;j<=m;j++)
		{
			if(a[i]==b[j])
			{
				f[i][j]=1;
				for(re k=1;k<j;k++)
					if(a[i]>b[k] and f[i-1][k]+1>f[i][j]) 
						f[i][j]=f[i-1][k]+1,pre[i][j]=k;
			}
			else f[i][j]=f[i-1][j],pre[i][j]=pre[i-1][j];
		}
	}
	/*for(re i=1;i<=n;i++)
	{
		for(re j=1;j<=m;j++)
		{
			if(f[i][j]>ans)
			{
				ans=f[i][j];
				pos=j;
			}
		}
	}*/
	for(re i=1;i<=m;i++)
	{
		if(f[n][i]>ans)
		{
			ans=f[n][i];
			pos=i;
		}
	}
	printf("%d\n",ans);
	for(;pos;pos=pre[n][pos]) sta.push(b[pos]);
	while(sta.size()) printf("%d ",sta.top()),sta.pop();
	return 0;
}

2021/11/19 21:42
加载中...