题意：给你一个字符串，对这个字符串有三种操作。
1）任意位置插入任意一个字符
2）任意位置删除一个字符
3）改变任意位置的一个字符。
问你最后要经过最少的步数使得这个字符串由两个相同的字符串串联构成。
解题思路：枚举将两个字符串分成两个串，然后对这两个串求改变k（0-len）次的最长公共子序列即可。
解题代码：
1 // BEGIN CUT HERE 2 /* 3 4 */ 5 // END CUT HERE 6 #line 7 "MakeSquare.cpp" 7 #include <cstdlib> 8 #include <cctype> 9 #include <cstring> 10 #include <cstdio> 11 #include <cmath> 12 #include <algorithm> 13 #include <vector> 14 #include <string> 15 #include <iostream> 16 #include <sstream> 17 #include <map> 18 #include <set> 19 #include <queue> 20 #include <stack> 21 #include <fstream> 22 #include <numeric> 23 #include <iomanip> 24 #include <bitset> 25 #include <list> 26 #include <stdexcept> 27 #include <functional> 28 #include <utility> 29 #include <ctime> 30 using namespace std; 31 32 #define PB push_back 33 #define MP make_pair 34 35 #define REP(i,n) for(i=0;i<(n);++i) 36 #define FOR(i,l,h) for(i=(l);i<=(h);++i) 37 #define FORD(i,h,l) for(i=(h);i>=(l);--i) 38 39 typedef vector<int> VI; 40 typedef vector<string> VS; 41 typedef vector<double> VD; 42 typedef long long LL; 43 typedef pair<int,int> PII; 44 45 char str[1000]; 46 int len ; 47 int dp[200][200][70]; 48 int solve(int x) 49 { 50 memset(dp,0,sizeof(dp)); 51 int same = 0 ; 52 for(int i = 1;i <= x ;i ++) 53 for(int j = x+1 ;j <= len ;j ++) 54 { 55 same = 0 ; 56 if(str[i] == str[j]) 57 { 58 same = 1; 59 } 60 if(same == 0 ) 61 for(int k = 0 ; k <= len ; k ++) 62 { 63 dp[i][j][k+1] = max(dp[i][j][k+1],dp[i-1][j-1][k] + 1); 64 } 65 66 for(int k = 0 ; k <= len; k ++) 67 { 68 dp[i][j][k] = max(dp[i][j][k],dp[i-1][j-1][k] + same); 69 dp[i][j][k] = max(dp[i][j][k],dp[i][j-1][k] ); 70 dp[i][j][k] = max(dp[i][j][k],dp[i-1][j][k] ); 71 } 72 } 73 int len1 = x; 74 int len2 = len - x; 75 //printf("%d %d %d ",len1,len2,dp[x][len]); 76 int ans = len; 77 for(int k = 0; k <= len; k ++) 78 { 79 ans = min(ans,len1 - dp[x][len][k] + len2 - dp[x][len][k] + k); 80 } 81 return ans; 82 } 83 class MakeSquare 84 { 85 public: 86 int minChanges(string S) 87 { 88 len = S.size(); 89 int ans = len; 90 for(int i = 0 ;i < len; i ++) 91 str[i+1] = S[i]; 92 for(int i = 1;i < len;i ++) 93 ans = min(ans,solve(i)); 94 return ans; 95 } 96 97 // BEGIN CUT HERE 98 public: 99 void run_test(int Case) { if ((Case == -1) || (Case == 0)) test_case_0(); if ((Case == -1) || (Case == 1)) test_case_1(); if ((Case == -1) || (Case == 2)) test_case_2(); if ((Case == -1) || (Case == 3)) test_case_3(); if ((Case == -1) || (Case == 4)) test_case_4(); } 100 private: 101 template <typename T> string print_array(const vector<T> &V) { ostringstream os; os << "{ "; for (typename vector<T>::const_iterator iter = V.begin(); iter != V.end(); ++iter) os << '"' << *iter << "","; os << " }"; return os.str(); } 102 void verify_case(int Case, const int &Expected, const int &Received) { cerr << "Test Case #" << Case << "..."; if (Expected == Received) cerr << "PASSED" << endl; else { cerr << "FAILED" << endl; cerr << " Expected: "" << Expected << '"' << endl; cerr << " Received: "" << Received << '"' << endl; } } 103 void test_case_0() { string Arg0 = "abcdabgcd"; int Arg1 = 1; verify_case(0, Arg1, minChanges(Arg0)); } 104 void test_case_1() { string Arg0 = "abcdeabce"; int Arg1 = 1; verify_case(1, Arg1, minChanges(Arg0)); } 105 void test_case_2() { string Arg0 = "abcdeabxde"; int Arg1 = 1; verify_case(2, Arg1, minChanges(Arg0)); } 106 void test_case_3() { string Arg0 = "aabcaabc"; int Arg1 = 0; verify_case(3, Arg1, minChanges(Arg0)); } 107 void test_case_4() { string Arg0 = "aaaaabaaaaabaaaaa"; int Arg1 = 2; verify_case(4, Arg1, minChanges(Arg0)); } 108 109 // END CUT HERE 110 111 }; 112 113 // BEGIN CUT HERE 114 int main() 115 { 116 MakeSquare ___test; 117 ___test.run_test(-1); 118 return 0; 119 } 120 // END CUT HERE