这题搞了很久很久。。弄得我都不想放上来了，但是想了想还是写上来吧，万一以后忘了怎么做了，又得搞很久很久了。题目是要求把一个字符串变成另外一个，每次可以选择一段字符串变成同一个字符，问最少用变多少次。本来想的更复杂，写了半天一直wa，后来发现自己想错了，，一不小心看到了kuangbin大牛说可以先由空串转化成b串。然后我想了一下，发现的确可以这样，这样就可以在由空串转化成b串的基础上判断a串与b串的区别，然后就可以得到由a串转化成b串的ans了。但是由空串转化成b串的时候假如b串是：acbdaefgha时，我求错了，调了很久才发现时这个串时是错的，于是改了一次啊就ac了。。。汗啊。。。硬着脸皮附上我写的超恶心的代码。
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath> #define LL long long
#define CLR(a, b) memset(a, b, sizeof(a))
#define SL(a) strlen(a) using namespace std;
const int N = 111;
const int INF = 1e7; char a[N], b[N];
int dp[N][N]; int main()
{
//freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
int i, j, len, k, t;
while(cin >> a >> b)
{
len = SL(a);
CLR(dp, 0);
for(i = 0; i < len; i ++)dp[i][i] = 1;
for(i = 1; i < len; i ++)
{
for(j = 0; j + i < len; j ++)
{
k = i + j;
dp[j][k] = INF;
for(t = j; t < k; t ++)
{
dp[j][k] = min(dp[j][k], dp[j][t] + dp[t + 1][k]);
if(b[t] == b[t + 1])
{
dp[j][k] = min(dp[j][k], dp[j][t] + dp[t + 1][k] - 1);
}
if(b[j] == b[k] && b[j] == b[t] && b[t] != b[t + 1])
{
dp[j][k] = min(dp[j][k], dp[j][t] + dp[t + 1][k] - 1);//我一直wa的那个地方。。。
}
}
if(b[j] == b[k])
{
dp[j][k] = min(dp[j][k], dp[j + 1][k - 1] + 1);
}
}
}
for(i = 0; i < len; i ++)
{
for(j = 0; j + i < len; j ++)
{
k = i + j;
for(t = j; t <= k; t ++)
{
dp[j][k] = min(dp[j][k], dp[j][t] + dp[t + 1][k]);
if(a[t] == b[t])
{
dp[j][k] = min(dp[j][k], dp[j][t - 1] + dp[t + 1][k]);
}
}
}
}
cout << dp[0][len - 1] << endl;
}
}