河南省汝州市文明建设门户网站,一对一视频网站开发,购物平台网站建设框架,兰州交通发展建设集团公司网站250pts RepeatString 题意#xff1a;问最少修改多少次将一个字符串修改为AA的形式。可以插入一个字符#xff0c;删除一个字符#xff0c;修改字符。 思路#xff1a;枚举分界点#xff0c;然后dp一下。 1 /*2 * Author: mjt3 * Date: 2018-10-17 19:50:164 * Last Mod…250pts RepeatString 题意问最少修改多少次将一个字符串修改为AA的形式。可以插入一个字符删除一个字符修改字符。 思路枚举分界点然后dp一下。 1 /*2 * Author: mjt3 * Date: 2018-10-17 19:50:164 * Last Modified by: mjt5 * Last Modified time: 2018-10-17 20:08:046 */7 #includebits/stdc.h8 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 i0; ip; i) a s[i];
22 for (int jp1; j(int)s.size(); j) b s[j];
23 for (int i0; i(int)a.size(); i) f[i][0] i;
24 for (int i0; i(int)b.size(); i) f[0][i] i;
25
26 for (int i1; i(int)a.size(); i)
27 for (int j1; 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 i0; i(int)s.size(); i) ans min(ans, solve(i, s));
36 return ans - 1;
37 }
38 }; 转载于:https://www.cnblogs.com/mjtcn/p/9806754.html
