学步园

大意略。

思路：这个DP说实话真的很难思考，根本无从下手的感觉，参考了该论文

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <string>
using namespace std;

const int MAXN = 72;

int f[MAXN][MAXN][MAXN], f1[MAXN][MAXN][MAXN], f2[MAXN][MAXN][MAXN];
char str1[MAXN], str2[MAXN], str3[MAXN];

void init()
{
	memset(f, 0, sizeof(f));
	memset(f1, 0, sizeof(f1));
	memset(f2, 0, sizeof(f2));
}

void read_case()
{
	init();
	scanf("%s%s%s", str1+1, str2+1, str3+1);
}

int dp()
{
	int len1 = strlen(str1+1), len2 = strlen(str2+1), len3 = strlen(str3+1);
	for(int i = 0; i <= len1; i++)
	{
		for(int j = 0; j <= len2; j++)
		{
			f[0][i][j] = f1[0][i][j] = f2[0][i][j] = 1;
		}
	}
	for(int i = 1; i <= len3; i++)
	{
		for(int j = 0; j <= len1; j++)
		{
			for(int k = 0; k <= len2; k++)
			{
				if(j)
				{
					f1[i][j][k] = f1[i][j-1][k];
					if(str1[j] == str3[i]) f1[i][j][k] += f[i-1][j-1][k];
					f1[i][j][k] %= 10007;
				}
				if(k)
				{
					f2[i][j][k] = f2[i][j][k-1];
					if(str2[k] == str3[i]) f2[i][j][k] += f[i-1][j][k-1];
					f2[i][j][k] %= 10007;
				}
				f[i][j][k] = (f1[i][j][k] + f2[i][j][k]) % 10007;
			}
		}
	}
	return f[len3][len1][len2] % 10007;
}

void solve()
{
	read_case();
	int ans = dp();
	printf("%d\n", ans);
}

int main()
{
	int T;
	scanf("%d", &T);
	while(T--)
	{
		solve();
	}
	return 0;
}