java超难编程题 挑战一下吧 大神帮吗发代码

Alice writes an English composition with a length of N characters. However, her teacher requires that M illegal pairs of characters cannot be adjacent, and if 'ab' cannot be adjacent, 'ba' cannot be adjacent either.

In order to meet the requirements, Alice needs to delete some characters.

Please work out the minimum number of characters that need to be deleted.

The first line contains the length of the composition N.

The second line contains N characters, which make up the composition. Each character belongs to 'a'..'z'.

The third line contains the number of illegal pairs M.

Each of the next M lines contains two characters ch1 and ch2,which cannot be adjacent.

For 20% of the data: 1 ≤ N ≤ 10

For 50% of the data: 1 ≤ N ≤ 1000

For 100% of the data: 1 ≤ N ≤ 100000, M ≤ 200.

One line with an integer indicating the minimum number of characters that need to be deleted.

Delete 'a' and 'd'.

6个回答

wynist 回复祈祷爱绝缘: 删除之后得到的串必然是原串的一个合法子序列，所以只需要求出最长的合法子序列x，结果即为n-x。对于你给出的bbbbabbbb，显然求得的是bbbbbbbb。

http://hihocoder.com/discuss/question/3960

import java.util.Arrays;
import java.util.Scanner;

public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
String str = scanner.next();
int m = scanner.nextInt();
boolean[][] concurrency = new boolean[26][26];
for (int i = 0; i < m; i++) {
String str1 = scanner.next();
concurrency[str1.charAt(0) - 'a'][str1.charAt(1) - 'a'] = true;
concurrency[str1.charAt(1) - 'a'][str1.charAt(0) - 'a'] = true;
}
solve(str, concurrency);
}
public static void solve(String str, boolean[][] concurrency) {
int n = str.length();
int[] dp = new int[n]; // dp[i]表示以i结尾的最长子满足条件子序列的长度
Arrays.fill(dp, 1);
char[] chars = str.toCharArray();
int res = 1;
for (int i = 1; i < n; i++) {
for (int j = 0; j < i; j++) {
if (!concurrency[chars[i] - 'a'][chars[j] - 'a']) {
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
res = Math.max(dp[i], res);
}
System.out.println(n - res);
}
}

import java.util.Scanner;

public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
String str = scanner.next();
int m = scanner.nextInt();
boolean[][] concurrency = new boolean[26][26];
for (int i = 0; i < m; i++) {
String str1 = scanner.next();
concurrency[str1.charAt(0) - 'a'][str1.charAt(1) - 'a'] = true;
concurrency[str1.charAt(1) - 'a'][str1.charAt(0) - 'a'] = true;
}
solve(str, concurrency);
}
public static void solve(String str, boolean[][] concurrency) {
int n = str.length();
int[][] dp = new int[n][26]; // dp[i][j]表示前i个字符的子串以('a' + j)结尾的最长子序列长度
char[] chars = str.toCharArray();
dp[0][chars[0] - 'a'] = 1;
for (int i = 1; i < n; i++) {
for (int j = 0; j < 26; j++) {
dp[i][j] = dp[i - 1][j];
}
int curIndex = chars[i] - 'a';
dp[i][curIndex] = 1;
for (int k = 0; k < 26; k++) {
if (!concurrency[k][curIndex]) {
dp[i][curIndex] = Math.max(dp[i][curIndex], dp[i - 1][k] + 1);
}
}
}
int res = 0;
for (int i = 0; i < 26; i++) {
res = Math.max(res, dp[n - 1][i]);
}
System.out.println(n - res);
}
}