HDU 1423 最長遞增公共子序列（LCIS）

時間 O(n*m)，空間 O(m) 可優化（滾動數組）。

代碼實現

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;

int max(int a, int b) { return a > b ? a : b; }

int main() {
    int T; scanf("%d", &T);
    while (T--) {
        int n, m;
        int a[510], b[510];
        int dp[510][510];
        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]);
        memset(dp, 0, sizeof(dp));
        for (int i = 1; i <= n; i++) {
            int maxv = 0;
            for (int j = 1; j <= m; j++) {
                dp[i][j] = dp[i-1][j];
                if (b[j] < a[i] && maxv < dp[i-1][j])
                    maxv = dp[i-1][j];
                if (a[i] == b[j])
                    dp[i][j] = maxv + 1;
            }
        }
        int ans = 0;
        for (int j = 1; j <= m; j++)
            ans = max(ans, dp[n][j]);
        printf("%d\n", ans);
        if (T) printf("\n");
    }
    return 0;
}

複雜度與優化

• 時間 O(T * n * m)，n,m≤500 完全足夠。
• 空間可優化為兩行滾動數組 O(m)。

總結

LCIS 結合了 LCS 和 LIS 的思想，通過在 LCS 的 DP 過程中維護「以當前值結尾的最長遞增長度」來實現。本題代碼簡潔，是 LCIS 模板題的優秀示例。