题解：P10954 LCIS

light_searcher · 2024-10-02 07:52:09 · 题解

首先，肯定是 dp。

设 f_{i,j} 表示 a 序列的前 i 个数和 b 序列中前 j 个数且以 b_j 为结尾的最长上升公共子序列，这里要注意 a_i 不一定是结尾。

为什么设一个这么奇怪的状态呢？我们可以想想其他状态。如果是以 a_i 为结尾且 b_j 为结尾，那么这个状态应该是错误的，因为我们无法保证 a_i = b_j。那么如果是 a 的前 i 个数和 b 的前 j 个数呢？你可以自己想想如何转移，反正我觉得这是极其复杂的。那么由此看来上文的状态应该是一个好的选择。

接下来进入正题，考虑如何转移。

分类讨论：

最后答案是 \max \{ f_{i,j} \}。

那么已经有了一个 \mathcal O(n^3) 的做法。

Code:

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=3e3+5;
int n,a[N],b[N],f[N][N],ans;
signed main(){
    scanf("%lld",&n);
    for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
    for(int i=1;i<=n;i++) scanf("%lld",&b[i]);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++){
            if(a[i]!=b[j]) f[i][j]=f[i-1][j];
            else{
                int mx=0;
                for(int k=1;k<j;k++)
                    if(b[k]<b[j]) mx=max(mx,f[i-1][k]);
                f[i][j]=mx+1;
            }
            ans=max(ans,f[i][j]);
        }
    printf("%lld",ans);
    return 0;
}

结果这么写常数很小，直接跑过了。

但是还是考虑继续优化。发现当 a_i =b_j 时由于 j 枚举时 i 不会变，所以如果 b_k < a_i，那么 f_{i-1,k} 就可以纳入到决策集合中，我们最终要用的是决策集合中的最大值，而这个值显然是只增不降的，那我们在枚举 j 的同时就可以完成对这个值的维护。

Code:

#include<bits/stdc++.h>
using namespace std;
const int N=3e3+5;
int n,a[N],b[N],f[N][N],ans;
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    for(int i=1;i<=n;i++) scanf("%d",&b[i]);
    for(int i=1;i<=n;i++){
        int val=0;
        for(int j=1;j<=n;j++){
            if(a[i]!=b[j]) f[i][j]=f[i-1][j];
            else f[i][j]=val+1;
            if(b[j]<a[i]) val=max(val,f[i-1][j]);
            ans=max(ans,f[i][j]);
        }
    }
    printf("%d",ans);
    return 0;
}