题目描述

　　给定两个整数序列，写一个程序求它们的最长上升公共子序列。

输入格式

　　每个序列用两行表示，第一行是长度L，第二行是该序列。

输出格式

　　在第一行，输出该LCIS的长度。第二行，输出该LCIS。

输入样例

1 4 2 5 -12

-12 1 2 4

输出样例

1 4

题解

　　表面上看起来是个$O(n^{4})$，但实际上可以优化到$O(n^{2})$（貌似还可以用树状数组优化到$O(nlogn)$）

　　我们设$dp[i][j]$为以$a_{1}$到$a_{i}$中的一个数和$b_{j}$为结尾的LCIS，容易得到当$a_{i} = b_{j}$时，$dp[i][j] = \underset{1 \leqslant k < j}{max} \left \{ dp[i - 1][k] + 1 \right \}$，否则$dp[i][j] = dp[i - 1][j]$。

　　其实我们可以在枚举$i$、$j$的时候顺便维护$\underset{1 \leqslant k < j}{max} \left \{ dp[i - 1][k] + 1 \right \}$，这样就把时间复杂度降到$O(n^{2})$了。

　　观察方程，其实我们第一位只会用到$i - 1$和$i$，这里又可以用滚动数组优化。

#include <iostream>

#define MAX_N (500 + 5)

#define MAX_M (500 + 5)

using namespace std;

int n, m;

int a[MAX_N], b[MAX_M];

int dp[MAX_M];

int p[MAX_M];

int ans;

void LCIS(int x)

{

    if(p[x]) LCIS(p[x]);

    cout << b[x] << " ";

    return;

}

int main()

{

    cin >> n;

    for(register int i = ; i <= n; ++i)

    {

        cin >> a[i];

    }

    cin >> m;

    for(register int i = ; i <= m; ++i)

    {

        cin >> b[i];

    }

    int pos = , tmp;

    for(register int i = ; i <= n; ++i)

    {

        tmp = ;

        for(register int j = ; j <= m; ++j)

        {

            if(a[i] > b[j] && dp[j] > dp[tmp]) tmp = j;

               if(a[i] == b[j])

            {

                dp[j] = dp[tmp] + ;

                p[j] = tmp;

            }

        }

    }

    for(register int i = ; i <= m; ++i)

    {

        if(dp[i] > dp[pos]) pos = i;

    }

    cout << dp[pos] << "\n";

    if(dp[pos]) LCIS(pos);

    return ;

}

参考程序

巴特西

【题解】LCIS

题目描述

输入格式

输出格式

输入样例

输出样例

题解

最新文章

热门文章