250pts RepeatString

题意：问最少修改多少次将一个字符串修改为AA的形式。可以插入一个字符，删除一个字符，修改字符。

思路：枚举分界点，然后dp一下。

1 /* 2 * @Author: mjt 3 * @Date:   2018-10-17 19:50:16 4 * @Last Modified by:   mjt 5 * @Last Modified time: 2018-10-17 20:08:04 6 */ 7 #include
     
       8 using namespace std; 9 typedef long long LL;10 11 const int N = 1005;12 13 int f[N][N];14 15 class RepeatString{16 public:17     int solve(int p,string s) {18         memset(f, 0x3f, sizeof(f));19         string a, b;20         a += '#', b += '#';21         for (int i=0; i<=p; ++i) a += s[i];22         for (int j=p+1; j<(int)s.size(); ++j) b += s[j];23         for (int i=0; i<(int)a.size(); ++i) f[i][0] = i;24         for (int i=0; i<(int)b.size(); ++i) f[0][i] = i;25         26         for (int i=1; i<(int)a.size(); ++i) 27             for (int j=1; j<(int)b.size(); ++j) {28                 f[i][j] = min(f[i][j], min(f[i - 1][j], f[i][j - 1]) + 1);29                 f[i][j] = min(f[i][j], f[i - 1][j - 1] + (a[i] != b[j]));30             }31         return f[a.size() - 1][b.size() - 1];32     }33     int minimalModify(string s) {34         int ans = s.size();35         for (int i=0; i<(int)s.size(); ++i) ans = min(ans, solve(i, s));36         return ans - 1;37     }38 };