#include<cstdio> #include<cstring> #include<cmath> #include<cstdlib> #include<iostream> #include<algorithm> #include<vector> #include<map> #include<queue> #include<stack> #include<string>#include<map> #include<set>#define eps 1e-6 #define LL long long using namespace std; const int maxn = 100 + 5;const int INF = 0x3f3f3f3f;char s[maxn], t[maxn];int cnt[maxn], d[maxn][maxn][30];int dp(int start, int end, char shua) {if(d[start][end][shua-'a'] != -1) return d[start][end][shua-'a'];if(start > end) return 0;if(start == end) return shua == t[start] ? 0 : 1;if(shua == t[end]) return dp(start, end-1, shua);int ans = INF;for(int i = end; i >= start; i–) {if(t[i] == t[end]) ans = min(ans, dp(start, i-1, shua)+dp(i, end, t[end])+1);}return d[start][end][shua-'a'] = ans;}void solve() {memset(d, -1, sizeof(d));int len = strlen(s);cnt[0] = s[0] == t[0] ? 0 : 1;for(int i = 1; i < len; i++) {if(s[i] == t[i]) cnt[i] = cnt[i-1];else {cnt[i] = INF;for(int j = i; j >= 0; j–){if(t[j] == t[i] && s[j] != t[j]) cnt[i] = min(cnt[i], dp(j+1,i-1,t[i])+1+(j>0 ? cnt[j-1]:0));}}}printf("%d\n", cnt[len-1]);}int main() {//freopen("input.txt", "r", stdin);while(scanf("%s%s", s, t) == 2) {solve(); }return 0;}
，我想，这就是旅行的真义吧。
