caioj 1073 动态规划入门（三维一边推：最长公共子序列加强版（三串LCS））

三维的与二维大同小异，看代码。

#include<cstdio>

#include<cstring>

#include<algorithm>

#define REP(i, a, b) for(int i = (a); i < (b); i++)

using namespace std;

const int MAXN = 112;

char a[MAXN], b[MAXN], c[MAXN];

int f[MAXN][MAXN][MAXN], path[MAXN][MAXN][MAXN];

void print(int x, int y, int z)

{

	int t = path[x][y][z];

	if(t == 1)

	{

		print(x - 1, y - 1, z - 1);

		putchar(a[x]);

	}

	else if(t == 2) print(x - 1, y, z);

	else if(t == 3) print(x, y - 1, z);

	else if(t == 4) print(x, y, z - 1);

}

int main()

{

	scanf("%s%s%s", a + 1, b + 1, c + 1);

	int lena = strlen(a + 1), lenb = strlen(b + 1), lenc = strlen(c + 1);

	REP(i, 1, lena + 1)

		REP(j, 1, lenb + 1)

			REP(k, 1, lenc + 1)

			{

				if(a[i] == b[j] && b[j] == c[k])

				{

					f[i][j][k] = f[i-1][j-1][k-1] + 1;

					path[i][j][k] = 1;

				}

				else

				{

					f[i][j][k] = max(f[i-1][j][k], max(f[i][j-1][k], f[i][j][k-1]));

					if(f[i][j][k] == f[i-1][j][k]) path[i][j][k] = 2;

					if(f[i][j][k] == f[i][j-1][k]) path[i][j][k] = 3;

					if(f[i][j][k] == f[i][j][k-1]) path[i][j][k] = 4;

				}

			}

	printf("%d\n", f[lena][lenb][lenc]);

	print(lena, lenb, lenc);

	return 0;

}

巴特西

caioj 1073 动态规划入门（三维一边推：最长公共子序列加强版（三串LCS））

最新文章

热门文章