2812_凤凰院真凶_dp

lzusa 发布于 2017-10-30 0 次阅读

题目描述

求LCIS(最长公共上升子序列)

 

思路

设f[i][j]表示a序列做到i，b序列做到j的LCIS

我们有O(n^3)的做法

当a[i]!=b[j]    f[i][j] = f[i-1][j]

a[i]==b[j]时，我们找到一个max f[i - 1][k] (b[k] < b[j])(k

 

然后显然可以构造数据卡掉这种做法

我们考虑直接记录max f[i - 1][k]即可

#include 
#define N 5001
#define max(x, y) ((x) > (y) ? (x) : (y))
int f[N][N], a[N], b[N];
int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    int m;
    scanf("%d", &m);
    for (int i = 1; i <= m; i++)
        scanf("%d", &b[i]);
    int ans = 0, mx = 0;
    for (int i = 1; i <= n; i++)
    {
        mx = 0;
        for (int j = 1; j <= m; j++)
        {
            if (a[i] != b[j])
            {
                f[i][j] = f[i - 1][j];
                if (b[j] < a[i]) mx = max(mx, f[i - 1][j]);
            }
            else
            {
                f[i][j] = mx + 1;
                if (b[j] < a[i]) mx = max(mx, f[i - 1][j]);
            }
            ans = max(ans, f[i][j]);
        }
    }
    printf("%d\n", ans);
}

 

]]>