light oj 1159 - Batman LCS

light oj 1159 - Batman LCS

学过简单动态规划的人应该对最长公共子序列的问题很熟悉了，这道题只不过多加了一条字符串变成三条了，还记得，只要把状态变成三维的即可。

//#include #include #include using namespace std;char str1[55];char str2[55];char str3[55];int dp[55][55][55];int maxval(int a, int b, int c){ a = max(a, b); a = max(a, c); return a;}int main(){ int t, kase = 0; scanf("%d", &t); while (t--) { int ans = 0; scanf("%s %s %s", &str1[1], &str2[1], &str3[1]); int l1 = strlen(&str1[1]); int l2 = strlen(&str2[1]); int l3 = strlen(&str3[1]); memset(dp, 0, sizeof(dp)); for (int i = 1; i <= l1; i++) { for (int j = 1; j <= l2; j++) { for (int k = 1; k <= l3; k++) { if (str1[i] == str2[j] && str2[j] == str3[k]) dp[i][j][k] = dp[i-1][j-1][k-1] + 1; else { dp[i][j][k] = maxval(dp[i-1][j][k], dp[i][j-1][k], dp[i][j][k-1]); } } } } printf("Case %d: %d\n", ++kase, dp[l1][l2][l3]); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。