C++(clang++ 11.0.1) 解法, 执行用时: 131ms, 内存消耗: 2436K, 提交时间: 2022-10-01 21:54:34

#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 504
#define inf -10000
#define setIO(s) freopen(s".in","r",stdin)
using namespace std;
int f[2][N][N];  
char A[N],B[N],C[N];  
void getmax(int &a,int b)
{
    if(b>a) a=b;
}
int main()
{
    // setIO("input");      
    int x,y,z,i,j,k; 
    scanf("%s%s%s",A+1,B+1,C+1);  
    x=strlen(A+1);
    y=strlen(B+1);
    z=strlen(C+1);   
    memset(f,-0x3f,sizeof(f));                                               
    f[0][0][0]=0;  
    int ans=0;     
    for(i=0;i<=x;++i)
    {
        int now=i%2;   
        f[now][0][0]=0;         
        for(j=0;j<=y;++j)
        {       
            for(k=0;k<=min(z,min(i,j));++k)          
            {
                if(i+j+k) f[now][j][k]=inf;                                           
                if(i) getmax(f[now][j][k],f[now^1][j][k]);         
                if(j) getmax(f[now][j][k],f[now][j-1][k]);    
                if(i&&j&&A[i]==B[j]) getmax(f[now][j][k],f[now^1][j-1][k]+(A[i]==B[j]));                 
                if(i&&j&&k&&(A[i]==B[j]&&B[j]==C[k])) getmax(f[now][j][k],f[now^1][j-1][k-1]+1); 
            }                                       
        }                 
    }                 
    if(max(f[0][y][z],f[1][y][z])<z) printf("NO SOLUTION\n"); 
    else printf("%d\n",max(f[0][y][z],f[1][y][z])); 
    return 0;
}