1 条题解
-
0
// 线性DP O(n^2) #include<bits/stdc++.h> using namespace std; const int N=10005; int n,m,a[N],b[N],ans; int f[N][N]; //f[i,j]表示前(i,j)个数且以 b[j] 为结尾的最长公共上升子序列的长度 int pre[N][N],path[N]; 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 mx=0,pos=0; for(int j=1;j<=m;j++){ if(a[i]!=b[j]) f[i][j]=f[i-1][j],pre[i][j]=j; else f[i][j]=mx+1,pre[i][j]=pos; if(a[i]>b[j]) if(f[i-1][j]>mx) mx=f[i-1][j],pos=j; } } int mm; for(int j=1;j<=m;j++)if(f[n][j]>ans){ ans=f[n][j]; mm=j; } int i=n,j=mm,cnt=0; while(i||j){ if(pre[i][j]!=j) path[++cnt]=b[j]; j=pre[i][j]; i--; } if(ans==0) {puts("0");return 0;} printf("%d\n",ans); for(int i=cnt;i>=1;i--)printf("%d ",path[i]); return 0; }
- 1
信息
- ID
- 2025
- 时间
- 2000ms
- 内存
- 1024MiB
- 难度
- 7
- 标签
- 递交数
- 85
- 已通过
- 19
- 上传者