250pts RepeatString
题意:问最少修改多少次将一个字符串修改为AA的形式。可以插入一个字符,删除一个字符,修改字符。
思路:枚举分界点,然后dp一下。
/*
* @Author: mjt
* @Date: 2018-10-17 19:50:16
* @Last Modified by: mjt
* @Last Modified time: 2018-10-17 20:08:04
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long LL; const int N = ; int f[N][N]; class RepeatString{
public:
int solve(int p,string s) {
memset(f, 0x3f, sizeof(f));
string a, b;
a += '#', b += '#';
for (int i=; i<=p; ++i) a += s[i];
for (int j=p+; j<(int)s.size(); ++j) b += s[j];
for (int i=; i<(int)a.size(); ++i) f[i][] = i;
for (int i=; i<(int)b.size(); ++i) f[][i] = i; for (int i=; i<(int)a.size(); ++i)
for (int j=; j<(int)b.size(); ++j) {
f[i][j] = min(f[i][j], min(f[i - ][j], f[i][j - ]) + );
f[i][j] = min(f[i][j], f[i - ][j - ] + (a[i] != b[j]));
}
return f[a.size() - ][b.size() - ];
}
int minimalModify(string s) {
int ans = s.size();
for (int i=; i<(int)s.size(); ++i) ans = min(ans, solve(i, s));
return ans - ;
}
};