P10954 LCIS

LCIS：把结尾值写进状态

问题

P10954 LCIS - 洛谷
求两个长度为 $n$ 的序列的最长公共上升子序列长度。

LCIS 同时有两个要求：它既是公共子序列，又严格递增。如果我们直接套用 LCS 的定义，会发现只记录两个前缀的答案不足以转移，因为新元素时还必须知道当前子序列的结尾值。

所以借用 LIS 的定义结合一下：$f[i][j]$ 表示只使用 $A_1\dots A_i$，并且以 $B_j$ 结尾的 LCIS 长度。于是我们把“结尾位置”写进状态后，递增限制就能通过比较 $B_j$ 处理。

接着考虑转移从 $i-1$ 推到 $i$ 时：

• 若 $A_i\ne B_j$，不能用 $A_i$ 与 $B_j$ 配对，继承 f[i-1][j]；
• 若 $A_i=B_j$，则在所有满足 $B_k<A_i$ 的旧状态后接上当前值：

$$f[i][j]=1+\max_{k<j,\ B_k<A_i}f[i-1][k]$$

但是如果直接枚举 $k$ 会得到 $O(n^3)$，我们发现对于 $k$ 这一层循环来说，$i$ 其实是一个常数，所以我们直接直接找到满足 $B_{j} < A_{i}$ 的最大的 f[i-1][j]，因为 $j$ 在逐渐扩展，所以可以直接省掉第三层循环。

▶

P10954

int a[maxn], b[maxn];
int f[maxn][maxn];
// a 序列前 i 个数，b 序列前 j 个数，且以 b[j] 结尾的最长公共子序列长度

void solve( ) {
    int n = read( );
    for( int i = 1; i <= n; ++ i ) a[i] = read( );
    for( int i = 1; i <= n; ++ i ) b[i] = read( );

    for( int i = 1; i <= n; ++ i ) {
        int mx = 0;
        for( int j = 1; j <= n; ++ j ) {
            if( a[i] != b[j] ) f[i][j] = f[i-1][j];
            else f[i][j] = mx + 1;
            if( b[j] < a[i] ) mx = max( mx, f[i-1][j] );
        }
    }
    
    int ans = 0;
    for( int j = 1; j <= n; ++ j ) ans = max( ans, f[n][j] );
    cout << ans << '\n';
}

• 时间复杂度：$O(n^2)$；
• 当前实现空间复杂度：$O(n^2)$；

记录

这题保留为 C 类记录。它把 LIS 中的“结尾值”与 LCS 中的“双序列匹配”结合起来；优化的关键不是换数据结构，而是在固定 $A_i$ 后用一次顺序扫描维护合法前驱的最优值。