题解 P2364 【胖男孩】

皎月半洒花

2019-01-04 19:55:22

Solution

嗝……又水一道DP…… 其实发这篇题解主要是讲$LCS$如何卡空间和时间的$qwq$ 首先$\Theta(n^3)$的$DP$不用说了。我们发现要输出方案——最简单的方法就是再开$O(n^3)$的数组来记录……但是吧,其实这些空间是**没有必要的**。 换句话说,这道题空间完全可以只开$16MB$。 我们思考,本题比较理想的输出路径是$\Theta(3n)$,即倒推法,沿着$pre_{L1,L2,L3}$不断向回找。但其实,对于每一个状态$dp_{i,j,k}$已知后,它是由$dp_{i-1,j,k},dp_{i,j-1,k},dp_{i,j,k-1}$还是$dp_{i-1,j-1,k-1}$转移过来的,已经确定了,那么$pre$数组就是十分多余的了,我们只需要一个$dfs:$ ```cpp inline void Print(int x, int y, int z){ if (!x || !y || !z) return ; if (dp[x][y][z] == dp[x - 1][y][z]) Print(x - 1, y, z) ; else if (dp[x][y][z] == dp[x][y - 1][z]) Print(x, y - 1, z) ; else if (dp[x][y][z] == dp[x][y][z - 1]) Print(x, y, z - 1) ; else if (dp[x][y][z] == dp[x - 1][y - 1][z - 1] + 1) Print(x - 1, y - 1, z - 1), putchar(A[x]) ; } ``` 然后$dp$的时候就可以直接用手写max优化常数而不是又长又慢的$\leq$了qwq 怎么说呢。。。其实渐进意义下,空间复杂度还是不变的$\Theta(n^3)$,但优化的效果的确十分显著$qwq$ ## $Code:$ ```cpp #include <cstdio> #include <cstring> #include <iostream> #define Bx 101 #define max mmax #define sr strlen using namespace std ; char A[Bx], B[Bx], C[Bx] ; int dp[Bx][Bx][Bx], LA, LB, LC ; inline void Print(int x, int y, int z){ if (!x || !y || !z) return ; if (dp[x][y][z] == dp[x - 1][y][z]) Print(x - 1, y, z) ; else if (dp[x][y][z] == dp[x][y - 1][z]) Print(x, y - 1, z) ; else if (dp[x][y][z] == dp[x][y][z - 1]) Print(x, y, z - 1) ; else if (dp[x][y][z] == dp[x - 1][y - 1][z - 1] + 1) Print(x - 1, y - 1, z - 1), putchar(A[x]) ; } inline int mmax(int a, int b){ return a > b ? a : b ;} int main(){ register int i, j, k ; cin >> A+1 >> B+1 >> C+1 ; LA = sr(A + 1), LB = sr(B + 1), LC = sr(C + 1) ; for (i = 1 ; i <= LA ; ++ i) for (j = 1 ; j <= LB ; ++ j) for (k = 1 ; k <= LC ; ++ k) if (A[i] == B[j] && B[j] == C[k]) dp[i][j][k] = dp[i - 1][j - 1][k - 1] + 1 ; else dp[i][j][k] = max(dp[i - 1][j][k], max(dp[i][j - 1][k], dp[i][j][k - 1])) ; Print(LA, LB, LC) ; return 0 ; } ```