#H 蓝肽子序列

时间限制: 1.0s 内存限制: 512.0MB 本题总分：20 分

问题描述

$L$ 星球上的生物由蛋蓝质组成，每一种蛋蓝质由一类称为蓝肽的物资首尾连接成一条长链后折叠而成。
生物学家小乔正在研究 $L$ 星球上的蛋蓝质。她拿到两个蛋蓝质的蓝肽序列，想通过这两条蓝肽序列的共同特点来分析两种蛋蓝质的相似性。
具体的，一个蓝肽可以使用 $1$ 至 $5$ 个英文字母表示，其中第一个字母大写，后面的字母小写。一个蛋蓝质的蓝肽序列可以用蓝肽的表示顺序拼接而成。
在一条蓝肽序列中，如果选取其中的一些位置，把这些位置的蓝肽取出，并按照它们在原序列中的位置摆放，则称为这条蓝肽的一个子序列。蓝肽的子序列不一定在原序列中是连续的，中间可能间隔着一些未被取出的蓝肽。
如果第一条蓝肽序列可以取出一个子序列与第二条蓝肽序列中取出的某个子序列相等，则称为一个公共蓝肽子序列。
给定两条蓝肽序列，找出他们最长的那个公共蓝肽子序列的长度。

输入格式

输入两行，每行包含一个字符串，表示一个蓝肽序列。字符串中间没有空格等分隔字符。

输出格式

输出一个整数，表示最长的那个公共蓝肽子序列的长度。

测试样例₁

Input：
LanQiaoBei
LanTaiXiaoQiao

Output：
2

Explanation：
最长的公共蓝肽子序列为 LanQiao，共两个蓝肽。

评测用例规模与约定

对于 $20$% 的评测用例，两个字符串的长度均不超过 $20$。
对于 $50$% 的评测用例，两个字符串的长度均不超过 $100$。
对于所有评测用例，两个字符串的长度均不超过 $1000$。

code：

import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Map;

public class Main {

    static int[] A, B;
    static int n, m, MAX = 0, cur;

    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        Map<String, Integer> map = new HashMap();
        String Astr = in.readLine();
        String Bstr = in.readLine();
        A = new int[1024];
        B = new int[1024];
        Integer val;
        String key;
        if (Astr.length() > Bstr.length()) {
            String t = Bstr;
            Bstr = Astr;
            Astr = t;
        }
        for (int start = 0, end, high = Astr.length(); start < high; start = end) {
            end = start + 1;
            while(end < high && Astr.charAt(end) > 'Z') end++;
            key = Astr.substring(start, end);
            val = map.get(key);
            if (val == null)
                map.put(key, val = cur++);
            A[n++] = val;
        }
        for (int start = 0, end, high = Bstr.length(); start < high; start = end) {
            end = start + 1;
            while(end < high && Bstr.charAt(end) > 'Z') end++;
            key = Bstr.substring(start, end);
            val = map.get(key);
            if (val != null)
                B[m++] = val;
        }
        dfs(0, 0, 0);
        System.out.println(MAX);
    }

    static void dfs(int Acur, int Bcur, int val) {
        if (Acur < n) {
            dfs(Acur + 1, Bcur, val);
            while (Bcur < m && A[Acur] != B[Bcur]) Bcur++;
            if (Bcur < m) dfs(Acur + 1, Bcur, val + 1);
        } else if (val > MAX) MAX = val;
    }
}

一眼就能知道是最长公共子序列问题，但好巧不巧

不会

所以比赛现场用的压缩减独加上暴搜，骗个五十分应该没啥问题
再上个现学的动规

import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Map;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        Map<String, Integer> map = new HashMap();
        String Astr = in.readLine();
        String Bstr = in.readLine();
        int n = 1, m = 1, cur = 1;
        int[] A = new int[1024];
        int[] B = new int[1024];
        Integer val;
        String key;
        if (Astr.length() > Bstr.length()) {
            String t = Bstr;
            Bstr = Astr;
            Astr = t;
        }
        for (int start = 0, end, high = Astr.length(); start < high; start = end) {
            end = start + 1;
            while(end < high && Astr.charAt(end) > 'Z') end++;
            key = Astr.substring(start, end);
            val = map.get(key);
            if (val == null)
                map.put(key, val = cur++);
            A[n++] = val;
        }
        for (int start = 0, end, high = Bstr.length(); start < high; start = end) {
            end = start + 1;
            while(end < high && Bstr.charAt(end) > 'Z') end++;
            key = Bstr.substring(start, end);
            val = map.get(key);
            if (val != null)
                B[m++] = val;
        }
        int[][] dp = new int[n + 1][m + 1];
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m; j++)
                dp[i][j] = A[i] == B[j] ? dp[i - 1][j - 1] + 1 : max(dp[i - 1][j], dp[i][j - 1]);
        System.out.println(dp[n][m] - 1);
    }

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

以上是《Java 蓝桥杯 国赛 第十一届 C组 试题H：蓝肽子序列》的全部内容，

感谢您对程序员阿鑫博客的支持！