UVA 10723 – Cyborg Genes [DP + LCS]

题目链接:http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=19469

题意:给定两个字符串,找到一个最短的串,使得输入的两个串均是他的子序列(不一定连续出现)。程序还应该统计长度最短的串的个数。

可以将题目转化为求两个字符串的最长公共子序列的长度和个数,两个串的总长度-最长公共子序列的长度即为最终答案。

其中dp[i][j]表示串1前i个字符与串2前j个字符的最长公共子序列长度,dp[i][j] = (str1[i]==str[j] ? dp[i-1][j-1] : max(dp[i-1][j] , dp[i][j-1] ))

#include <cstdio>
#include <string>
#include <iostream>
#include <cstring>
using namespace std;

int dp[35][35], cnt[35][35];

int main(){
	int T, kase = 0; cin >> T; cin.get();
	while (T--){
		char str1[35], str2[35];
		gets(str1+1); gets(str2+1);
		memset(dp, 0, sizeof(dp)); memset(cnt, 0, sizeof(cnt));
		int len1 = strlen(str1 + 1), len2 = strlen(str2 + 1);
		for (int i = 0; i <= len1; ++i) cnt[i][0] = 1;
		for (int i = 0; i <= len2; ++i) cnt[0][i] = 1;
		for (int i = 1; i <= len1; ++i){
			for (int j = 1; j <= len2; ++j){
				if (str1[i] == str2[j]){
					dp[i][j] = dp[i - 1][j - 1] + 1;
					cnt[i][j] = cnt[i - 1][j - 1];
				}
				else{
					if (dp[i - 1][j] > dp[i][j - 1]){
						dp[i][j] = dp[i - 1][j];
						cnt[i][j] = cnt[i - 1][j];
					}
					else if (dp[i - 1][j] < dp[i][j - 1]){
						dp[i][j] = dp[i][j - 1];
						cnt[i][j] = cnt[i][j - 1];
					}
					else {
						dp[i][j] = dp[i - 1][j];
						cnt[i][j] = cnt[i - 1][j] + cnt[i][j - 1];
					}
				}
			}
		}
		printf("Case #%d: %d %d\n", ++kase, len1 + len2 - dp[len1][len2], cnt[len1][len2]);
	}
	return 0;
}

 

欢迎留言