题目描述
X星球的考古学家发现了一批古代留下来的密码。
这些密码是由A、B、C、D 四种植物的种子串成的序列。
仔细分析发现,这些密码串当初应该是前后对称的(也就是我们说的镜像串)。
由于年代久远,其中许多种子脱落了,因而可能会失去镜像的特征。
你的任务是:
给定一个现在看到的密码串,计算一下从当初的状态,它要至少脱落多少个种子,才可能会变成现在的样子。
输入格式
共一行,包含一个由大写字母ABCD构成的字符串,表示现在看到的密码串。
输出格式
输出一个整数,表示至少脱落了多少个种子。
数据范围
输入字符串长度不超过1000
输入样例1:
ABCBA
输出样例1:
0
输入样例2:
ABDCDCBABC
输出样例2:
3
算法1
(字符串反转后求公共子序列) $O(n^2)$
blablabla就是把原字符串进行反转,形成原字符串A,反转字符串B,然后求出二者最长公共子序列的长度,用字符串长度减去这个长度即可。可以粗略感受一下,当一个字符串以某一个字符x
为分界点的时候,它是最中间1个,它前面有n
个跟后面相同的字符对应,后面有n
个跟前面对应,加起来就是2n+1
然后中间的x
是不必要总是存在的,它可以是0可以是1。那么对应过来,其实就是A跟B的最长公共子序列的长度。
参考文献:y总
Java 代码
//package ac_0329_区间dp;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
static int N = 1010;
static int n;
static char a[] = new char[N];
static char b[] = new char[N];
static int f[][] = new int[N][N];
//反转后采取最长公共子序列的方法求解
public static void main(String[] args) throws IOException {
// TODO Auto-generated method stub
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String str = br.readLine();
n = str.length();
a = (" "+str).toCharArray();
for (int i = n; i >= 1; i--) {
b[n-i+1] = a[i];
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if(a[i]==b[j]) f[i][j] = f[i-1][j-1] + 1;
else {
f[i][j] = Math.max(f[i][j-1], f[i-1][j]);
}
}
}
System.out.println(n-f[n][n]);
}
}
算法2
(区间dp) $O(n^2)$
blablabla就是分4种情况考虑,区间左右端点相等,那么就左右2边各收缩1然后,公共字符+2,如果不同,那么左右两边分别收缩1,取较大值。需要注意的是,当l==r
的时候它是回文的,公共字符数为1。
参考文献:y总
Java 代码
//package ac_0329_区间dp;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
static int N = 1010;
static int n;
static char a[] = new char[N];
static int f[][] = new int[N][N];
public static void main(String[] args) throws IOException {
// TODO Auto-generated method stub
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String str = br.readLine();
n = str.length();
a = (" "+str).toCharArray();
for (int i = 1; i <= n; i++) {
f[i][i] = 1;
}
for (int len = 2; len <= n; len++) {
for (int i = 1; i+len-1 <= n; i++) {
int l = i;
int r = l + len - 1;
f[l][r] = Math.max(f[l][r-1], f[l+1][r]);//这样写更优雅 这种情况一定存在
if(a[l]==a[r]) f[l][r] = Math.max(f[l][r], f[l+1][r-1] + 2);//如果左右两边的字符相同
}
}
System.out.println(n-f[1][n]);
}
}