意甲冠军：

按标题给4操作模式  用最少的次数  离a串行转换b弦

思路：

因为操作仅仅有这4种  所以我们能够确定从头到位去匹配a和b一定是正确的

那么状态数一共同拥有多少呢  一共同拥有length[a]*length[b]*(1+num(a~z)+num(A~Z))  状态不多  能够用dp解决

上述计算状态能够表示为dp[i][j][k]  即a串匹配到i同一时候b串匹配到j  k表示改动后缀操作改动成的字符

那么仅仅须要打表出全部的dp  同一时候利用dp+(lena-i)+(lenb-j)更新ans就可以

代码：

#include<cstdio>

#include<iostream>

#include<cstring>

#include<string>

#include<algorithm>

#include<map>

#include<set>

#include<vector>

#include<queue>

#include<cstdlib>

#include<ctime>

#include<cmath>

using namespace std;

typedef unsigned long long LL;

#define N 505

#define M 53

#define inf 100000000

int ans;

int dp[N][N][M];

char f[N], g[N];

int change(char u) {

	if (u >= 'A' && u <= 'Z')

		return u - 'A' + 1;

	if (u >= 'a' && u <= 'z')

		return u - 'a' + 27;

	return 0;

}

int main() {

	int i, j, k, ans, lf, lg;

	while (~scanf("%s", f)) {

		if (!strcmp(f, "#"))

			break;

		scanf("%s", g);

		lf = strlen(f);

		lg = strlen(g);

		for (i = 0; i <= lf; i++) {

			for (j = 0; j <= lg; j++) {

				for (k = 0; k < M; k++)

					dp[i][j][k] = inf;

			}

		}

		ans = inf;

		dp[0][0][0] = 0;

		for (i = 0; i <= lf; i++) {

			for (j = 0; j <= lg; j++) {

				for (k = 0; k < M; k++) {

					if (dp[i][j][k] == inf)

						continue;

					ans = min(ans, dp[i][j][k] + lf - i + lg - j);

					if (i == lf || j == lg)

						continue;

					if ((!k && f[i] == g[j]) || (k && k == change(g[j]))) {

						//same

						dp[i + 1][j + 1][k] = min(dp[i + 1][j + 1][k],

								dp[i][j][k]);

					} else {

						//delete

						dp[i + 1][j][k] = min(dp[i + 1][j][k], dp[i][j][k] + 1);

						//insert

						dp[i][j + 1][k] = min(dp[i][j + 1][k], dp[i][j][k] + 1);

						//change

						dp[i + 1][j + 1][k] = min(dp[i + 1][j + 1][k],

								dp[i][j][k] + 1);

						//Suffix change

						dp[i + 1][j + 1][change(g[j])] = min(

								dp[i + 1][j + 1][change(g[j])],

								dp[i][j][k] + 1);

					}

				}

			}

		}

		printf("%d\n", ans);

	}

	return 0;

}