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<bits/stdc++.h> 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 };

?

轉載于:https://www.cnblogs.com/mjtcn/p/9806754.html

總結

以上是生活随笔為你收集整理的SRM 698 div1 RepeatString的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。