CF10D LCIS

_Chesed_ · 2023-06-18 23:07:59 · 个人记录

CF10D LCIS

思路

既然题目要求既是 CS ，又是 IS ，a[i] 与 b[j] 是否是合法的匹配，有两个要求：

a[i]=b[j]
上一个选择位置 a[p]=b[q]，a[p]<a[i] ，b[q]<b[j]。

那么可以考虑子序列DP，设 f[i][j] 表示第一个子序列以 a[i] 结尾，第二个子序列以 b[j] 结尾的 LCIS 长度，有：

f[i][j]=\max(f[p][q]+1\vert a[p]=a[q] \&a[p]<a[i]\&b[q]<b[j]\&a[i]=a[j])

时间复杂度 O(n^2m^2) ，显然无法通过。

优化

优化一

记录的后效性状态太多导致转移时间复杂度过高，因此考虑精简状态的记录。

由于公共子序列的性质，因此两个子序列中选择的值一定完全相同，而枚举末尾位置只是为了确定是否满足上升子序列的性质。

因此，只需要枚举其中一个序列的末尾元素用于判断，另一个序列只需要合法且最长即可：

设 f[i][j] 表示第一个序列以 a[i] 结尾、第二个序列考虑前 j 个元素的 LCIS 长度，有：

f[i][j-1] ,& a[i]\neq b[j]\\ \max(f[k][j-1]\vert k\in[1,i-1],a[k]<a[i])+1,& a[i]=b[j]\\ \end{cases}

时间复杂度 O(n^2m) 。

优化二

使用前缀优化求出：

maxx[i][j]=\max(f[k][j-1]\vert k\in[1,i-1],a[k]<a[i])

由于使用 maxx 数组时一定有 a[k]<a[i]=b[j] ，因此：maxx[i][j]=\max(f[k][j-1]\vert k\in[1,i-1],a[i]<b[j])=\max(maxx[i-1][j],f[i-1][j-1] )a[i-1]<b[j]
时间复杂度 O(nm) 。

Code

#include<bits/stdc++.h>
using namespace std;
#define MAXN 100005
int q[MAXN],a[MAXN],b[MAXN];
int pos[MAXN];
int maxx[505][505],f[505][505];
struct Node{
    int a,b;
}maxx_pos[505][505],f_pos[505][505];
map<int ,int> b_pos;
void print(int pos_a,int pos_b){
    if(pos_a==0) return;//边界条件 
    print(f_pos[pos_a][pos_b].a,f_pos[pos_a][pos_b].b); 
    cout<<a[pos_a]<<' ';
}
int main(){
    int n,m;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    cin>>m;
    for(int i=1;i<=m;i++){
        cin>>b[i];
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            maxx[i][j]=maxx[i-1][j];
            maxx_pos[i][j]=maxx_pos[i-1][j];
            if(a[i-1]<b[j]&&f[i-1][j-1]>maxx[i][j]){
                maxx[i][j]=f[i-1][j-1];
                maxx_pos[i][j]={i-1,j-1};
            }
            f[i][j]=f[i][j-1];
            f_pos[i][j]=f_pos[i][j-1];
            if(a[i]==b[j]&&maxx[i][j]+1>f[i][j]){
                f[i][j]=maxx[i][j]+1;
                f_pos[i][j]=maxx_pos[i][j];
            }
        }
    }
    int ans=0,pos=0;
    for(int i=1;i<=n;i++){
        if(f[i][m]>ans){
            ans=f[i][m];
            pos=i;//记录答案位置 
        }
    }
    cout<<ans<<'\n';
    print(pos,m);//递归输出 
}