学过简单动态规划的人应该对最长公共子序列的问题很熟悉了，这道题只不过多加了一条字符串变成三条了，还记得，只要把状态变成三维的即可。
//http://lightoj.com/volume_showproblem.php?problem=1159 //2013-08-15-09.50 #include <iostream> #include <stdio.h> #include <algorithm> #include <string.h> 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; }
