这题搞了很久很久。。弄得我都不想放上来了，但是想了想还是写上来吧，万一以后忘了怎么做了，又得搞很久很久了。题目是要求把一个字符串变成另外一个，每次可以选择一段字符串变成同一个字符，问最少用变多少次。本来想的更复杂，写了半天一直wa，后来发现自己想错了，，一不小心看到了kuangbin大牛说可以先由空串转化成b串。然后我想了一下，发现的确可以这样，这样就可以在由空串转化成b串的基础上判断a串与b串的区别，然后就可以得到由a串转化成b串的ans了。但是由空串转化成b串的时候假如b串是：acbdaefgha时，我求错了，调了很久才发现时这个串时是错的，于是改了一次啊就ac了。。。汗啊。。。硬着脸皮附上我写的超恶心的代码。
#include#include #include #include #include #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; }}