2015 - 平方字符串
Time Limit : 1 秒
Memory Limit : 128 MB
定义“平方字符串”，意思为一个字符串s[1…n]，其中子串s1[1…k]和s2[k+1…n]完全相等。例如”abab”,”aaaa”是平方字符串，”aba”,”abca”就不是
有如下几种操作：
1. 将任意一个字符替换成另外一个字符
2. 可以在字符串的任意一个地方插入一个字符
3. 可以删去字符串的任意一个字符
给一个初始字符串，问经过上述操作最少几次能够将该字符串变成“平方字符串”。
Input
第一行输入一个数T，表示测试数据个数，对于每个测试数据输入一个字符串，表示初始的字符串，字符串长度<=100
Output
对于每个测试数据输出一个数，表示最少操作次数。
Examples
Input Format
3 abcdabcmd abcdabyd abcdabcd
Output Format
1 1 0
Solution C++
#include<cstdio> #include<algorithm> #include<vector> #include<cstring> #include<stack> #include<iostream> #include<queue> #include<cmath> #include<string> #include<set> #include<map> using namespace std; const int maxn = 100 + 5; const int mod = 1000000000 + 7; const double eps = 1e-7; const int INF = 1000000000; typedef long long LL; typedef pair<int, int> P; char s[maxn]; int dp[maxn][maxn]; int solve(int s1, int e1, int s2, int e2){ memset(dp, 0, sizeof dp); int tag = 0; for(int i = s2;i <= e2;i++){ if(s[0]==s[i]) tag = 1; if(tag) dp[0][i] = i-s2; else dp[0][i] = i-s2+1; } tag = 0; for(int i = s1;i <= e1;i++){ if(s[s2]==s[i]) tag = 1; if(tag == 1) dp[i][s2] = i-s1; else dp[i][s2] = i-s1+1; } for(int i = s1+1;i <= e1;i++){ for(int j = s2+1;j <= e2;j++){ if(s[i]==s[j]) dp[i][j] = dp[i-1][j-1]; else{ dp[i][j] = min(dp[i-1][j-1], min(dp[i-1][j], dp[i][j-1]))+1; } } } return dp[e1][e2]; } int main(){ int t; scanf("%d", &t); while(t--){ scanf("%s", s); int n = strlen(s); if(n == 1){ printf("1\n"); continue; } int ans = n; int s1 = 0, e1; int s2, e2 = n-1; for(int i = 0;i < n-1;i++){ e1 = i; s2 = i+1; //cout << solve(s1, e1, s2, e2) << endl; ans = min(ans, solve(s1, e1, s2, e2)); } printf("%d\n", ans); } return 0; }