Skip to content

11072: 【原1072】小X的生物实验

题目

题目描述

author: 寿鹤鸣 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1072

Description

小X梦见他来到了一个神奇的星球,这个星球上生物的DNA序列由无数种碱基对构成,

更奇怪的是,组成DNA序列的每一种碱基在该序列中正好出现5次!这样如果一个DNA序列有N种不同的碱基构成,那么它的长度一定是5N。

若从一个DNA序列(字符串)s中任意抽取一些碱基(字符),将它们仍按在s中的顺序排列成一个新串u,则称u是s的一个子序列。对于两

个DNA序列s1和s2,如果存在一个序列u同时成为s1和s2的子序列,则称u是s1和s2的公共子序列。

小X已知两个DNA序列s1, s2,求s1和s2的最长公共子序列的长度。

Input Format

第一行一个整数N,表示这个星球上某种生物使用了N种不同的碱基,以后将它们编号为1…N的整数。

以下还有两行,每行描述一个DNA序列:包含5N个1…N的整数,整数之间由一个空格隔开,且每一个整数在对应的序列中正好出现5次。

Output Format

只有一个整数,即两个DNA序列的最大匹配数目。

Hint

60%的测试数据中:\(1 \leq N \leq 1000\)

100%的测试数据中:\(1 \leq N \leq 20000\)

Sample Input

2
1 1 2 2 1 1 2 1 2 2
1 2 2 2 1 1 2 2 1 1

Sample Output

7

FineArtz's solution

/* 小X的生物实验 */
#include <iostream>
using namespace std;

int pos[1000005][5], a[1000005];
int n;

inline int lowbit(int x){
    return x & (-x);
}

void change(int x, int y){
    while (x <= n){
        a[x] = max(a[x], y);
        x += lowbit(x);
    }
}

int find(int x){
    int ret = 0;
    while (x != 0){
        ret = max(ret, a[x]);
        x -= lowbit(x);
    }
    return ret;
}

int main(){
    cin >> n;
    n *= 5;
    for (int i = 1; i <= n; ++i){
        int x, j = 0;
        cin >> x;
        while (pos[x][j])
            ++j;
        pos[x][j] = i;
    }
    int ans = 0;
    for (int i = 1; i <= n; ++i){
        int x;
        cin >> x;
        for (int j = 4; ~j; --j){
            int t = find(pos[x][j] - 1) + 1;
            ans = max(t, ans);
            change(pos[x][j], t);
        }
    }
    cout << ans << endl;
    return 0;
}

yyong119's solution

#include <iostream>
#define MAX_N 20005
using namespace std;
int n;
int a[MAX_N * 5], tree[MAX_N * 5];
int map[MAX_N][6];
inline int read() {
    char ch = getchar(); int flag = 1, res = 0;
    while (ch != '-' && (ch < '0' || ch > '9')) ch = getchar();
    if (ch == '-') flag = -1, ch = getchar();
    while (ch >= '0' && ch <= '9') res = res * 10 + ch - '0', ch = getchar();
    return res * flag;
}
void update(int x, int num) {
    for (; x <= n * 5; x += x & -x)
        tree[x] = max(tree[x], num);
}
int query(int x) {
    int res = 0;
    for (; x; x -= x & -x)
        res = max(res, tree[x]);
    return res;
}
int main() {
    n = read();
    for (int i = 1; i <= n * 5; ++i) a[i] = read();
    for (int i = 1; i <= n * 5; ++i) {
        int tmp = read();
        map[tmp][++map[tmp][0]] = i;
    }
    for (int i = 1; i <= n * 5; ++i)
        for (int j = 5; j >= 1; --j)
            update(map[a[i]][j], query(map[a[i]][j] - 1) + 1);
    cout << query(n * 5) << endl;
    return 0;
}