求助WA on #17
  • 板块CF10D LCIS
  • 楼主cbkxx
  • 当前回复0
  • 已保存回复0
  • 发布时间2023/11/9 10:00
  • 上次更新2023/11/9 14:24:12
查看原帖
求助WA on #17
705343
cbkxx楼主2023/11/9 10:00
#include<bits/stdc++.h>
using namespace std;
int n,m,a[505],b[505],dp[505][505],pre[505][505],maxn,posj;
void print(int j){
	if(j==0)return;
	print(pre[n][j]);
	cout<<b[j]<<" ";
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i];
	cin>>m;
	for(int j=1;j<=m;j++)cin>>b[j];
	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];
				pre[i][j]=pre[i-1][j];
			}
			else{
				dp[i][j]=1;
				int pos_j=0;
				for(int k=j-1;k>=1;k--){
					if(dp[i-1][k]+1>dp[i][j]&&b[k]<b[j]){
						dp[i][j]=dp[i-1][k]+1;
						pos_j=k;
					}
				}
				pre[i][j]=pos_j;
			}
			if(dp[i][j]>maxn){
				maxn=dp[i][j];
				posj=j;
			}
		}
	}
	cout<<maxn<<endl;
	print(posj);
	return 0;
}

k正着枚举样例都过不去!

2023/11/9 10:00
加载中...