【CSP模拟赛】凤凰院凶真（最长公共上升子序列）

题目描述

α世界线.凤凰院凶真创立了反抗SERN统治的组织“瓦尔基里”.为了脱离α线,他需要制作一个世界线变动率测量仪.

测量一个世界线相对于另一个世界线的变动率,实质上就是要求出这两个世界线的最长公共合法事件序列.

一个世界线的事件逻辑序列是一个正整数序列,第k个数表示第k个事件发生的时间.对于一个世界线,一个合法的事件序列是事件逻辑序列的一个子序列,满足时间严格递增.

现在,对于两个不同的世间线α,β求出最长的一个事件序列,满足这个序列在α，β世界线中均是合法的.这个序列也就是之前提到过的最长公共合法事件序列.

输入描述

第一行一个整数n,表示世界线α的事件个数.

第二行n个整数a1;a2......an,表示世界线的事件逻辑序列.

第三行一个整数m,表示世界线β的事件个数.

第四行m个整数b1;b2......bm,表示世界线的事件逻辑序列.

输出描述

第一行一个整数k,表示最长公共合法事件序列的长度.

第二行k个整数,表示最长公共合法事件序列.如果有多解,输出任意一个.

样例输入

5
1 4 2 5 1
4
1 1 2 4

样例输出

1 4

分析

虽然听机房的大佬们说这是一道最长公共上升子序列的板子题，然而我不会。。。。。。

根据最长公共序列的求法，可以考虑二维状态dp[i][j]

如果dp[i][j]表示a序列前i个事件，b序列前j个事件构成的最长公共上升子序列的长度，转移时因为不知道最后一项的大小所以无法转移

如果dp[i][j]表示a序列第i个事件，b序列第j个事件作为结尾的最长公共上升子序列的长度，转移时因为不知道前一项在哪里所以要疯狂枚举状态从而达到O（n^4）的优秀复杂度

可以试着折中一下，

用dp[i][j]表示a序列前i个事件，b序列前j个事件构成且以b序列的第j个事件为结尾的最长公共上升子序列的长度。

所以dp[i][j]就可以由dp[i-1][1~j-1]转移过来，而且这个东西还可以利用单调性优化

因为更新dp[i]这一维的时候，i是不变的，所以可以一遍dp一遍存下并维护dp[i-1][1~j](a[i]>b[j])的最大值

这样就可以从O(n^3)优化到O(n^2)了只有我这样的菜文鸡一个板题才写这么多东西

Code

#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=5005;
int n,m,x,y,en,ans,a[maxn],b[maxn],sta[maxn],dp[maxn][maxn],pre[maxn][maxn];
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++)for(int j=1;j<=m;j++)
    {
        dp[i][j]=dp[i-1][j];
        if(b[j]==a[i])dp[i][j]=dp[i-1][pre[i][0]]+1,pre[i][j]=pre[i][0];
        if(b[j]<a[i]&&dp[i-1][pre[i][0]]<dp[i-1][j])pre[i][0]=j;
        if(ans<dp[i][j]&&a[i]==b[j])ans=dp[x=i][y=j];
    }
    printf("%d
",ans);
    do
    {
        sta[++en]=b[y];y=pre[x][y];
        while(a[x]!=b[y])x--;
    }while(y);
    while(en)printf("%d%c",sta[en],en==1?'
':' '),en--;
}