hdu 4545 魔法串（金山居）

本文主要是介绍hdu 4545 魔法串（金山居），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

就是一个求最长公共子序列的水题

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std;
#define MAXN 1005
int dp[MAXN][MAXN];
char s1[MAXN], s2[MAXN];
char ch1[2], ch2[2];
bool hash[128][128];
int Max(int a, int b)
{return (a > b) ? a : b;
}
int main()
{int T;int cas = 0;for(scanf("%d", &T); T--; ){scanf("%s%s", s1 + 1, s2 + 1);int m;scanf("%d", &m);memset(hash, 0, sizeof(hash));while(m--){scanf("%s%s", ch1, ch2);hash[ch1[0]][ch2[0]] = 1;}int len1 = strlen(s1 + 1);int len2 = strlen(s2 + 1);memset(dp, 0, sizeof(dp));for(int i = 1; i <= len2; ++i){for(int j = 1; j <= len1; ++j){dp[i][j] = Max(dp[i - 1][j], dp[i][j - 1]);if((s2[i] == s1[j]) || (hash[s2[i]][s1[j]]))dp[i][j] = Max(dp[i][j], dp[i - 1][j - 1] + 1);}}if(dp[len2][len1] == len1)printf("Case #%d: happy\n", ++cas);elseprintf("Case #%d: unhappy\n", ++cas);}return 0;
}

这篇关于hdu 4545 魔法串（金山居）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---