hihoCoder 1039文字最も詳細な問題解決レポートを削除

7095 ワード

タイトルソース:文字消去
問題解決の考え方:
1、指定された文字列の任意の位置に'A'、'B'、'C'の任意の文字を挿入し、挿入後の文字が消去された後で最も短い文字列長を計算する.
2、文字消去後の最短長さを計算する時、知能的に一度計算して、個人は何ももっと良い方法を考え出せなかった.
3、1文字ずつ挿入した後、2ステップ目の計算を経て最も短い文字列長min、最後に元の文字列の長さ-min+1を記録する.
 
具体的なアルゴリズム(java版、直接AC可能)
 
 1 import java.util.Scanner;
 2 
 3 public class Main {
 4 
 5     public static int handle(StringBuffer buffer) {
 6         int count = 0;
 7         while (true) {
 8             StringBuffer temp = new StringBuffer();
 9             int i = 0, j = 1;
10             for (; j < buffer.length(); j++) {
11                 if (buffer.charAt(i) != buffer.charAt(j)) {
12                     temp.append(buffer.charAt(i));
13                 } else {
14                     while (j < buffer.length()
15                             && buffer.charAt(i) == buffer.charAt(j))
16                         j++;
17                 }
18                 i = j;
19             }
20             if (j == buffer.length()) {
21                 temp.append(buffer.charAt(i));
22             }
23             if (temp.length() == buffer.length()) {
24                 count = temp.length();
25                 break;
26             }
27             buffer = temp;
28         }
29         return count;
30     }
31 
32     public static void main(String[] args) {
33         Scanner scanner = new Scanner(System.in);
34         int n = scanner.nextInt();
35         for (int i = 0; i < n; i++) {
36             StringBuffer buffer = new StringBuffer(scanner.next());
37             int min = buffer.length();
38             for (int j = 0; j < buffer.length(); j++) {
39                 for (char ch = 'A'; ch <= 'C'; ch++) {
40                     StringBuffer temp = new StringBuffer(buffer);
41                     temp = temp.insert(j, ch);
42                     int count = handle(temp);
43                     min = min > count ? count : min;
44                 }
45             }
46             System.out.println(buffer.length() + 1 - min);
47         }
48     }
49 }