hdu 1516 LCS (编辑距离+记录路径)

注意输出的格式与内容
DP很简单了LCS
传送门

//MADE BY Y_is_sunshine;
//#include <bits/stdc++.h>
//#include <memory.h>
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <sstream>
#include <cstdio>
#include <vector>
#include <string>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <math.h>

#define INF 0x3f3f3f3f
#define MAXN 100005
#define maxn 105

const int mod = 1e9 + 7;

using namespace std;

char s1[105];
char s2[105];
int dp[105][105];
int len1, len2;

void init(void) {
	memset(dp, 0x3f, sizeof(dp));
	for (int i = 0; i <= len1; i++)
		dp[i][0] = i;
	for(int i = 0; i <= len2; i++)
		dp[0][i] = i;
}

void f1(void) {
	int i = len1;
	int j = len2;
	int cnt = 0;
	while (i||j) {
		if (dp[i][j] == dp[i - 1][j - 1] && s1[i] == s2[j]) {
			i--, j--;
		}
		else if (dp[i][j] == dp[i - 1][j - 1] + 1 && i && j) {
			printf("%d Replace %d,%c\n", ++cnt, i, s2[j]);
			i--, j--;
		}
		else if (dp[i][j] == dp[i - 1][j] + 1 && i) {
			printf("%d Delete %d\n", ++cnt, i);
			i--;
		}
		else if(j){
			printf("%d Insert %d,%c\n", ++cnt, i + 1, s2[j]);
			j--;
		}
	}
}

int main()
{
	freopen("data.txt", "r", stdin);

	while (~scanf("%s%s", s1 + 1, s2 + 1)) {
		len1 = strlen(s1 + 1);
		len2 = strlen(s2 + 1);
		init();
		for (int i = 1; i <= len1; i++) {
			for (int j = 1; j <= len2; j++) {
				if (s1[i] == s2[j])
					dp[i][j] = min(dp[i][j], dp[i - 1][j - 1]);
				else
					dp[i][j] = min(min(dp[i - 1][j] + 1, dp[i][j - 1] + 1), dp[i - 1][j - 1] + 1);
			}
		}

		printf("%d\n", dp[len1][len2]);
		f1();

	}
	


	freopen("CON", "r", stdin);
	system("pause");
	return 0;
}