HDU 3831 DICS

제목:
문제에서 제시한 4가지 조작을 통해 가장 적은 횟수로 a열에서 b열로 바꾸다
아이디어:
조작은 이 네 가지밖에 없기 때문에 우리는 처음부터 끝까지 a와 b가 반드시 정확하다는 것을 확정할 수 있다
그럼 상태수가 총 몇 개냐면length[a]*length[b]*(1+num(a~z)+num(A~Z)) 상태가 많지 않으니 dp로 해결할 수 있어요.
상기 계산 상태는 dp[i][j][k]로 표시할 수 있다. 즉, a열이 i에 일치하고 b열이 jk에 일치하면 접미사 수정 작업이 수정된 문자를 나타낼 수 있다.
그러면 모든 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
", ans);
	}
	return 0;
}