HDU 5904 LCIS(动态规划)解题报告

2016-09-27 207 次浏览 解题报告

题目链接

题目大意

给定两个序列 a, b,求它们的最长公共子序列,这个子序列必须是值连续递增的,如 3, 4, 5, 6 。

解题思路

本题给出了一个限制条件,即子序列是值连续递增的序列,无形之中降低了难度。我们可以用数组 c 来表示以 1, 2, ..., i, ... 结尾的最长值连续递增子序列的长度,不难看出 c[i] = c[i-1]+1 。于是,我们只需要把原序列从头到尾扫一遍即可得到 c 数组。

栗如,a 序列为:1, 3, 2, 3, 5 ,扫一遍原序列即可得到以 i 结尾的最长值连续递增子序列的长度 ca[i]:
ca[1] = 1;
ca[3] = ca[2] + 1 = 1;
ca[2] = ca[1] + 1 = 2;
ca[3] = ca[2] + 1 = 3;
ca[5] = ca[4] + 1 = 1;

求出序列 a, b 对应的 ca, cb 数组之后,它们以 i 结尾的公共最长值连续递增子序列长度为 ca[i], cb[i] 中值较小的一个,即 min(ca[i], cb[i]) 。我们只需要遍历从 1 遍历到 10^5(题目中 a[i], b[i] 的最大值是 10^6,实际测试数据中不超过 10^5,如果真的按它的 10^6 做很容易被卡超时,也是醉了,厉害了我的出题哥),找寻最大值即可。

参考代码

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

const int MAXN = 100000;
int a[MAXN+1], b[MAXN+1];
int ca[MAXN+1], cb[MAXN+1];

int main(int argc, char const *argv[]) {
    int t, n, m;
    scanf("%d", &t);
    while(t--) {
        scanf("%d %d", &n, &m);
        memset(ca, 0, sizeof ca);
        memset(cb, 0, sizeof cb);
        for(int i=0; i<n; ++i) {
            scanf("%d", &a[i]);
            ca[a[i]] = ca[a[i]-1] + 1;
        }
        for(int i=0; i<m; ++i) {
            scanf("%d", &b[i]);
            cb[b[i]] = cb[b[i]-1] + 1;
        }
        int ans = 0;
        for(int i=1; i<=MAXN; ++i) {
            ans = max(ans, min(ca[i], cb[i]));
        }
        printf("%d\n", ans);
    }
    
    return 0;
}

bLue 创作,采用 知识共享署名 3.0,可自由转载、引用,但需署名作者且注明文章出处。
本文地址:https://dreamer.blue/blog/post/2016/09/27/hdu-5904.dream

还不快抢沙发

添加新评论