1 条题解

  • 0
    @ 2025-12-1 21:21:12
    // 线性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

    E5_4 [CF10D] 最长公共上升子序列LCIS2️⃣(spj)

    信息

    ID
    2025
    时间
    2000ms
    内存
    1024MiB
    难度
    7
    标签
    递交数
    85
    已通过
    19
    上传者