侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 470 篇文章
  • 累计创建 108 个标签
  • 累计收到 9 条评论

目 录CONTENT

文章目录

【动态规划, LCS】密码脱落【蓝桥杯】

GabrielxD
2022-09-12 / 0 评论 / 0 点赞 / 22 阅读 / 1,040 字 / 正在检测是否收录...

题目

试题 历届真题 密码脱落【第七届】【省赛】【C组】

1222. 密码脱落

P1435 [IOI2000] 回文字串 / [蓝桥杯 2016 省] 密码脱落


X星球的考古学家发现了一批古代留下来的密码。

这些密码是由A、B、C、D 四种植物的种子串成的序列。

仔细分析发现,这些密码串当初应该是前后对称的(也就是我们说的镜像串)。

由于年代久远,其中许多种子脱落了,因而可能会失去镜像的特征。

你的任务是:

给定一个现在看到的密码串,计算一下从当初的状态,它要至少脱落多少个种子,才可能会变成现在的样子。

输入格式

共一行,包含一个由大写字母ABCD构成的字符串,表示现在看到的密码串。

输出格式

输出一个整数,表示至少脱落了多少个种子。

数据范围

输入字符串长度不超过1000

输入样例1:

ABCBA

输出样例1:

0

输入样例2:

ABDCDCBABC

输出样例2:

3

解题

方法一:DFS(递归)(超时)

思路

对于给定的字符串可以从两边开始比对,讨论需要恢复多少个字符能达到镜像的效果。
如果左右镜像位置的字符相同则不需要恢复字符,但是如果不同就需要讨论恢复左边字符还是恢复右边字符。
那么就可以使用递归方式求解:

  • 维护两个指针分别指向字符串两端。
  • 如果左右两边指向的字符相同,则递归两个指针都向中间推进一位的情况。
  • 否则分别递归左指针推进一位(模拟在右侧补了一位字符)和右指针推进一位(模拟在左侧补了一位字符)的情况,取较小的脱落数返回。
  • 递归的结束条件是:左右指针相撞。
  • 剪枝的条件是:当前脱落数已经大于维护的最小脱落数。

如图是当输入字符串为 ABDCDCBABC 时反推出的所有原字符串的可能:

时间复杂度:O(2n)O(2^n)
在题目给定 1000 的数据范围下会超时。

代码

import java.util.*;
import java.io.*;

public class Main {
    static char[] chs;
    static int minCnt = Integer.MAX_VALUE;
    
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        chs = in.readLine().toCharArray();
        System.out.println(dfs(0, chs.length - 1, 0));
    }
    
    static int dfs(int left, int right, int cnt) {
        if (cnt >= minCnt) return minCnt;
        if (left >= right) {
            if (cnt < minCnt) minCnt = cnt;
            return cnt;
        }
        if (chs[left] == chs[right]) return dfs(left + 1, right - 1, cnt);
        else return Math.min(dfs(left + 1, right, cnt + 1), dfs(left, right - 1, cnt + 1));
    }
}

方法二:动态规划

思路

要求原字符串是左右对称的,也就是回文串,那么可以把原串翻转一下,原串与翻转串能匹配上的子序列就是原来就有的回文字符,这样的话原串长度减去该子序列的长度就是脱落的种子数。需要脱落的种子数尽量少,那么原有的回文字符就应该尽量多,也就是应该求原串与翻转串的 LCS (最长公共子序列)

LCS 问题是经典的动态规划题,详见:【动态规划, LCS】最长公共子序列

代码

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        String str = in.readLine();
        String revStr = new StringBuilder(str).reverse().toString();
        System.out.println(str.length() - lcs(str, revStr));
    }
    
    static int lcs(String str1, String str2) {
        int m = str1.length(), n = str2.length();
        char[] chs1 = str1.toCharArray(), chs2 = str2.toCharArray();
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 1; i <= m; ++i) {
            char c1 = chs1[i - 1];
            for (int j = 1; j <= n; ++j) {
                char c2 = chs2[j - 1];
                if (c1 == c2) dp[i][j] = dp[i - 1][j - 1] + 1;
                else dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
        return dp[m][n];
    }
}
0

评论区