UVA - 10723 类似LCS

思路：dp(i, j)表示第一个串前i个字符和第二个串前j个字符需要的最短字符串长度，cnt(i, j)表示第一个串前i个字符和第二个串前j个字符需要的最短字符串的个数。

转移方程：

if(s1[i] == s2[j]) dp[i][j] = dp[i-1][j-1] + 1;
else dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1]);

if(s1[i] == s2[j]) cnt[i][j] = cnt[i-1][j-1]; //字符成功匹配
else {
	if(dp[i-1][j] == dp[i][j-1])
	        cnt[i][j] = cnt[i-1][j] + cnt[i][j-1];
	else if(dp[i-1][j] < dp[i][j-1])
		cnt[i][j] = cnt[i-1][j];
	else
		cnt[i][j] = cnt[i][j-1];
}

AC代码

#include <cstdio>
#include <cmath>
#include <cctype>
#include <algorithm>
#include <cstring>
#include <utility>
#include <string>
#include <iostream>
#include <map>
#include <set>
#include <vector>
#include <queue>
#include <stack>
using namespace std;
#pragma comment(linker, "/STACK:1024000000,1024000000")
#define eps 1e-10
#define inf 0x3f3f3f3f
#define PI pair<int, int>
typedef long long LL;
const int maxn = 30 + 5;
char s1[maxn], s2[maxn];
int dp[maxn][maxn], cnt[maxn][maxn];
int main() {
	int T, kase = 1;
	scanf("%d", &T);
	getchar();
	while(T--) {
		fgets(s1+1, sizeof(s1), stdin);
		fgets(s2+1, sizeof(s2), stdin);
		//scanf("%s%s", s1+1, s2+1);
		int n = strlen(s1+1) - 1, m = strlen(s2+1) - 1;
		for(int i = 0; i < maxn; ++i) {
			dp[0][i] = dp[i][0] = i;
			cnt[0][i] = cnt[i][0] = 1;
		}
		for(int i = 1; i <= n; ++i)
			for(int j = 1; j <= m; ++j) {
				if(s1[i] == s2[j]) dp[i][j] = dp[i-1][j-1] + 1;
				else dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1]);
			}
		for(int i = 1; i <= n; ++i)
			for(int j = 1; j <= m; ++j) {
				if(s1[i] == s2[j]) cnt[i][j] = cnt[i-1][j-1];
				else {
					if(dp[i-1][j] == dp[i][j-1])
						cnt[i][j] = cnt[i-1][j] + cnt[i][j-1];
					else if(dp[i-1][j] < dp[i][j-1])
						cnt[i][j] = cnt[i-1][j];
					else
						cnt[i][j] = cnt[i][j-1];
				}
		}
		printf("Case #%d: %d %d\n", kase++, dp[n][m], cnt[n][m]);
	}
	return 0;
}

如有不当之处欢迎指出！

巴特西

UVA - 10723 类似LCS

最新文章

热门文章