统计
  • 建站日期:2021-03-10
  • 文章总数:699 篇
  • 评论总数:733 条
  • 分类总数:10 个
  • 最后更新:12月4日
文章 精密算法

Java 蓝桥杯 国赛 第十一届 C组 试题H:蓝肽子序列

程序员阿鑫
首页 精密算法 正文


Java蓝桥杯国赛第十一届C组试题H:蓝肽子序列
-程序员阿鑫-带你一起秃头!
-第1
张图片

#H 蓝肽子序列

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


问题描述

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


输入格式

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


输出格式

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

测试样例1

Input:
LanQiaoBei
LanTaiXiaoQiao

Output:
2

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

评测用例规模与约定

对于 20 2020% 的评测用例,两个字符串的长度均不超过 20 2020
对于 50 5050% 的评测用例,两个字符串的长度均不超过 100 100100
对于所有评测用例,两个字符串的长度均不超过 1000 10001000


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:蓝肽子序列
-程序员阿鑫-带你一起秃头!
-第2
张图片

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

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

版权说明
文章采用: 《署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0)》许可协议授权。
版权声明:未标注转载均为本站原创,转载时请以链接形式注明文章出处。如有侵权、不妥之处,请联系站长删除。敬请谅解!

-- 展开阅读全文 --
这篇文章最后更新于2021-1-4,已超过 1 年没有更新,如果文章内容或图片资源失效,请留言反馈,我们会及时处理,谢谢!
Java 蓝桥杯 国赛 第十一届 C组 试题I:画廊
« 上一篇
Java 蓝桥杯 国赛 第十一届 C组 试题G:皮亚诺曲线距离
下一篇 »
为了防止灌水评论,登录后即可评论!
注册登录

HI ! 请登录
注册会员,享受下载全站资源特权。
登陆 注册
上号,带你一起秃头!

IP地址

热门文章

1
抖音无限礼物模拟小工具分享
2
QQ假红包引流QQ群教程及代码
4
卡QQ永久大会员方法

最新文章

标签