题目描述：
YXY 发现好多计算机中的单词都是缩写，如 GDB，它是全称 Gnu DeBug 的缩写。但是，有时缩写对应的全称并不固定，如缩写 LINUX，可以理解为：
（1）LINus's UniX （2）LINUs's miniX （3）Linux Is Not UniX
现在 YXY 给出一个单词缩写，以及一个固定的全称（由若干个单词组成，用空格分隔）。全称中可能会有无效的单词，需要忽略掉，一个合法缩写要求每个有效的单词中至少有一个
字符出现在缩写中，缩写必须按顺序出现在全称中。对于给定的缩写和一个固定的全称，问有多少种解释方法。解释方法为缩写的每个字母出现在全称中每个有效单词中的位置，有一个字母位置不同，就认为是不同的解释方法。
输入格式：
第一行输入一个 N，表示有 N 个无效单词；接下来 N 行分别描述一个由小写字母组成的无效单词；接下来是若干个询问，先给出缩写（只有大写字母），然后给出一个全称。读
入以“LAST CASE”结束。
输出格式：
对于每个询问先输出缩写，如果当前缩写不合法。则输出“is not a valid abbreviation”，否则输出“can be formed in i ways”（i 表示解释方法种数）。
样例输入 ：
2
and
of
ACM academy of computer makers
RADAR radio detection and ranging
LAST CASE
样例输出：
ACM can be formed in 2 ways
RADAR is not a valid abbreviation
数据范围 ： 1<=N<=100，每行字符串长度不超过 150，询问不超过 20，所给数据计算出
来的最后方案数不超过 10^9。
数据范围很小，此题暴力修改+一般DP
贴代码：
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<queue>
using namespace std;
typedef long long LL;
inline int read()
{
int x=,f=;char c=getchar();
while(!isdigit(c)){if(c=='-')f=-;c=getchar();}
while(isdigit(c)){x=x*+c-'';c=getchar();}
return x*f;
}
int n,l1,l2,l3;
char s[],sc[][],mb[],t[];
bool judge(char *a,char *b)
{
int x=strlen(a),y=strlen(b);
if(x!=y)return ;
for(int i=;i<x;i++)
if(a[i]!=b[i])return ;
return ;
}
int main()
{
freopen("abbr.in","r",stdin);
freopen("abbr.out","w",stdout);
n=read();
for(int i=;i<n;i++)scanf("%s",sc[i]);
cin.getline(s,);
while()
{
char tmp[];
memset(tmp,,sizeof(tmp));
memset(mb,,sizeof(mb));
memset(s,,sizeof(s));
cin.getline(tmp,);
if(!strcmp(tmp,"LAST CASE"))break;
int l0=strlen(tmp);;bool ok=;
l1=l2=l3=;
int i = ;
while(tmp[i] != ' ') mb[l1++] = tmp[i++];
for(i++; i < l0; i++) s[l2++] = tmp[i];
// printf("%s\n%s\n", mb, s);
ok=;
int st=,en=,now=;
bool had[];
memset(had,,sizeof(had));
memset(tmp,,sizeof(tmp));
memset(t, , sizeof(t));
for(i = ; i < l2;) {
char tw[]; int tcnt = ;
while(i < l2 && s[i] != ' ') {
tw[tcnt++] = s[i];
i++;
}
i++;
tw[tcnt] = ;
bool ok = ;
for(int j = ; j < n; j++) if(!strcmp(sc[j], tw)) {
ok = ; break;
}
if(!ok) continue;
for(int j = ; j < tcnt; j++) t[l3++] = tw[j];
t[l3++] = ' ';
}
l3--;
// printf("%s %s\n", mb, t);
int cnt=;
for(int i=;i<l3;i++) if(t[i]==' ')cnt++;
if(cnt>l1)
{
printf("%s is not a valid abbreviation\n",mb);
continue;
}
int dp[][][];
memset(dp,,sizeof(dp));
for(int i=l1;i>=;i--)mb[i]=mb[i-];
for(int i=l3;i>=;i--)t[i]=t[i-];
// printf("new: %s %s\n", mb + 1, t + 1);
dp[][][]=;
for(int i=;i<=l3;i++)
{
if(t[i]==' ')continue;
for(int j=;j<=min(i,l1);j++)
{
// printf("%d %d: %d %d\n", i, j, dp[i][j][0], dp[i][j][1]);
if(t[i+]==' ')
{
if(t[i+]-'a'==mb[j+]-'A')dp[i+][j+][]+=dp[i][j][];
dp[i+][j][]+=dp[i][j][];
continue;
}
if(t[i+]-'a'==mb[j+]-'A')dp[i+][j+][]+=(dp[i][j][]+dp[i][j][]);
dp[i+][j][]+=dp[i][j][];dp[i+][j][]+=dp[i][j][];
}
}
for(int i=;i<=l1;i++)printf("%c",mb[i]);
if(!dp[l3][l1][])printf(" is not a valid abbreviation\n");
else printf(" can be formed in %d ways\n",dp[l3][l1][]); }
return ;
}