题解 P2364 【胖男孩】

嗝……又水一道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:

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:

#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 ;
}