Description：

给三个字符串 $A,B,C$ ，求 $A,B$ 的最长公共子序列，满足 $C$ 是这个子序列的子序列。

$1\le len \le 500$

Solution：

记 $f[i][j][k]$ 表示三个字符串分别到了 $i,j,k$ 位置，初值是 $A$ 和 $B$ 的 $LCS$ 数组，然后转移只是比普通 $LCS$ 多加了一个 $C$ 的转移，即如果加了新字符刚好和 $C[k]$ 相同，那么 $C$ 也可以有上一个转移过来，注意由于强制 $C$ 跑满，所以 $k>0$ 的状态初值都要赋成 $-INF$ 。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

#define MAXL 510

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

int la,lb,lc;

int f[MAXL][MAXL][2];

#define NEG 0xc0c0c0c0

int main()

{

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

    la = strlen(a + 1);lb = strlen(b + 1);lc = strlen(c + 1);

    int cur = 0;

    for(int i = 1;i <= la;++i)

    {

        for(int j = 1;j <= lb;++j)

        {

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

            if(a[i] == b[j])f[i][j][cur] = max(f[i][j][cur],f[i - 1][j - 1][cur] + 1);

        }

    }

    for(int k = 1;k <= lc;++k)

    {

        cur = cur ^ 1;

        for(int i = 0;i <= la;++i)

            for(int j = 0;j <= lb;++j)

                f[i][j][cur] = NEG;

        for(int i = 1;i <= la;++i)

        {

            for(int j = 1;j <= lb;++j)

            {

                if(a[i] == b[j])

                {

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

                    if(a[i] == c[k])

                    {

                        f[i][j][cur] = max(f[i][j][cur],f[i - 1][j - 1][cur ^ 1] + 1);

                    }

                }

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

            }

        }

        

    }

    if(f[la][lb][cur] > 0)cout << f[la][lb][cur] << endl;

    else puts("NO SOLUTION");

    return 0;

}