hihocoder 神奇字符串

思路：
暴力，模拟。
实现：
 1 #include <iostream>
 2 #include <algorithm>
 3 #include <cstdio>
 4 #include <string>
 5 #include <cstring>
 6 using namespace std;
 7 
 8 const int INF = 0x3f3f3f3f;
 9 
10 void str_swap(string & x, int i, int j)
11 {
12     char tmp = x[i];
13     x[i] = x[j];
14     x[j] = tmp;
15 }
16 
17 int cal(string x, string y)
18 {
19     int s = x.length();
20     int t = y.length();
21     if (s != t)
22         return INF;
23     int cnt = 0;
24     for (int i = 0; i < t; i++)
25     {
26         if (x[i] == y[i])
27             continue;
28         bool flag = false;
29         for (int j = i + 1; j < s; j++)
30         {
31             if (x[j] == y[i])
32             {
33                 for (int k = j; k > i; k--)
34                 {
35                     str_swap(x, k, k - 1);
36                     cnt++;
37                 }
38                 flag = true;
39                 break;
40             }
41         }
42         if (!flag)
43         {
44             return INF;
45         }
46     }
47     return cnt;
48 }
49 
50 int main()
51 {
52     string a, b;
53     cin >> a >> b;
54     int n = b.length();
55     int minn = INF;
56     for (int i = 0; i <= n; i++)
57     {
58         for (char c = 'a'; c <= 'z'; c++)
59         {
60             string tmp = b;
61             tmp.insert(i, 1, c);
62             minn = min(minn, cal(a, tmp));
63         }
64     }
65     for (int i = 0; i < n; i++)
66     {
67         for (char c = 'a'; c <= 'z'; c++)
68         {
69             string tmp = b;
70             tmp.erase(i, 1);
71             minn = min(minn, cal(a, tmp));
72         }
73     }
74     for (int i = 0; i < n; i++)
75     {
76         for (char c = 'a'; c <= 'z'; c++)
77         {
78             string tmp = b;
79             tmp[i] = c;
80             minn = min(minn, cal(a, tmp));
81         }
82     }
83     cout << minn << endl;
84     return 0;
85 }
总结：
学习了string 类 insert(可以在最后一个字符后面的位置插入字符或者字符串), erase方法。