求助递归输出方案
  • 板块CF10D LCIS
  • 楼主Patronus
  • 当前回复1
  • 已保存回复1
  • 发布时间2023/10/31 12:59
  • 上次更新2023/11/2 10:34:22
查看原帖
求助递归输出方案
533297
Patronus楼主2023/10/31 12:59
#include<bits/stdc++.h>
using namespace std;
const int N=505;
int f[N][N],a[N],b[N],ans[N][N],p;
int n,m,res;
int read(){
    int x=0,f=1;
    char c=getchar();
    while(!isdigit(c) && c!='-') c=getchar();
    if(c=='-') f=-1,c=getchar();
    while(isdigit(c)) x=(x<<3)+(x<<1)+(c^48),c=getchar();
    return x*f;
}
void print(int i,int j){
    if(!j) return;
    if(ans[n][j]){
        print(n-1,j-1);
        printf("%d ",b[j]);
    }
    else print(n,j-1);
}
int main(){
    //freopen(Name ".in", "r", stdin);
    //freopen(Name ".out", "w", stdout);
    n=read();
    for(int i=1;i<=n;i++) a[i]=read();
    m=read();
    for(int i=1;i<=m;i++) b[i]=read();
    a[0]=b[0]=-1;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(a[i]==b[j]){
                for(int k=0;k<j;k++){
                    if(b[k]<a[i] && f[i][j]<f[i-1][k]+1){
                        f[i][j]=f[i-1][k]+1;
                        ans[i][j]=k;
                    }
                }
            }
            else{
                f[i][j]=f[i-1][j];
                ans[i][j]=ans[i-1][j];
            }
        }
        
    }
    for(int i=1;i<=m;i++){
        if(res<f[n][i]){
            res=f[n][i];        
            p=i;
        }
    }
    printf("%d\n",res);
    print(n,p);
    return 0;
}
2023/10/31 12:59
加载中...