2024/10/16 upd：更改了 update 的写法。

description

题目讲得很清楚了，唯一的坑点是缩写中，不一定一个字母对应一个单词。

solution

看一眼数据范围，$len \le 150$，考虑 dp。

读入

先：

cin>>s[0];//读入第一行缩写

然后再 while 循环处理：

while(1){
    cin>>s[++sum];
    if(mp[s[sum]]){//去除无效字母
        sum--;
        continue;
    }
    if(sum==1&&s[0]=="LAST"&&s[1]=="CASE"){//结束条件
        break;
    }
    if(s[sum][0]>='A'&&s[sum][0]<='Z'){//开始处理的条件，即读到缩写就处理上一行
        sum--;//把下一行的缩写踢出去

以及：

s[0]=s[sum+1];//将下一行缩写存到s[0]
sum=0;

dp 实现

设 $dp_{i,j}$ 表示前 $i$ 个单词缩写，对应前 $j$ 个字母的方案数。那么，根据乘法原理和加法原理，可得转移为：

$$ dp_{i,j} = \sum_{k = i-1}^{j - 1} sum_{i,k,j-1} dp_{i-1,k} $$

记 $s$ 为缩写从第 $k$ 到第 $j-1$ 个字母的子串，则 $sum _{i,k,j-1}$ 表示 $s$ 在第 $i$ 个单词中出现的次数。而求 $sum$ 的过程刚好对应求 $s$ 与第 $i$ 个单词最长公共子序列的长度刚好为 $s$ 的长度的计数。而我们有 P2516 最长公共子序列。

至于求和为什么是从 $i-1$ 到 $j-1$。因为一个单词至少对应一个缩写字母，前 $i-1$ 个单词要对应 $i-1$ 个字母，所以下界为 $i-1$。同理，第 $i$ 个单词至少要对应一个字母，所以上界为 $j-1$。

于是，欢愉地 AC 了。

code

//#pragma GCC optimize(3,"Ofast","inline")
#include<bits/stdc++.h>
using namespace std;
int max(int a,int b){
    return a>b?a:b;
}
int min(int a,int b){
    return a<b?a:b;
}
int read(){
    int x=0,lcs=1;
    char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-'){
            lcs=-1;
        }
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        x=(x<<1)+(x<<3)+(c^'0');
        c=getchar();
    }
    return x*lcs;
}
void write(int x){
    if(x<0){
        putchar('-');
        x=-x;
    }
    if(x>9){
        write(x/10);
    }
    putchar(x%10+'0');
    return;
}
int n,sum,i,j,ans,k,dp[151][151],lcs[2][151],num[2][151];
char c;
string fei[101],s[152],ss;
pair<int,int> dpp(int k,int l,int rr){
    int i,j;
    string a=" ",b=" "+s[k];
    for(i=l;i<=rr;i++){
        a=a+s[0][i];
    }
    int n=a.size()-1,m=b.size()-1,now=1,pre=0;
    for(i=0;i<=m;i++){
        num[0][i]=1; 
        num[1][i]=0;
        lcs[0][i]=0;
        lcs[0][i]=0;
    }
    num[1][0]=1;
    for(i=1;i<=n;i++){
        for(j=1;j<=m;j++){
            lcs[now][j]=max(lcs[pre][j],lcs[now][j-1]);
            num[now][j]=0;
            if(a[i]+32==b[j]){
                lcs[now][j]=max(lcs[now][j],lcs[pre][j-1]+1); 
            }
            if(a[i]+32==b[j]&&lcs[now][j]==lcs[pre][j-1]+1){
                num[now][j]+=num[pre][j-1];
            }
            if(lcs[pre][j]==lcs[now][j]){
                num[now][j]+=num[pre][j];
            }
            if(lcs[now][j-1]==lcs[now][j]){
                num[now][j]+=num[now][j-1];
            }
            if(lcs[pre][j-1]==lcs[now][j]){
                num[now][j]-=num[pre][j-1];
            }
        }
        now=pre;pre=1-pre;
    }
    return {lcs[pre][m],num[pre][m]};
}
map<string,bool> mp;
int main(){
    //freopen("abbr.in","r",stdin);
    //freopen("abbr.out","w",stdout);
    n=read();
    for(i=1;i<=n;i++){
        cin>>fei[i];
        mp[fei[i]]=1;
    }
    if(n!=0){
        c=getchar();    
    }
    cin>>s[0];
    while(1){
        cin>>s[++sum];
        if(mp[s[sum]]){
            sum--;
            continue;
        }
        if(sum==1&&s[0]=="LAST"&&s[1]=="CASE"){
            break;
        }
        if(s[sum][0]>='A'&&s[sum][0]<='Z'){
            sum--;
            for(i=0;i<=sum;i++){
                for(j=0;j<=s[0].size();j++){
                    dp[i][j]=0;
                }
            }
            for(i=1;i<=s[0].size()-sum+1;i++){
                pair<int,int> tmp=dpp(1,0,i-1);
                if(tmp.first==i){
                    dp[1][i]=tmp.second;
                }
                else{
                    break;
                }
            }
            for(i=2;i<=sum;i++){
                for(j=i;j<=s[0].size()-sum+i;j++){
                    for(k=j-1;k>=i-1;k--){
                        pair<int,int> tmp=dpp(i,k,j-1);
                        if(tmp.first==j-k){
                            dp[i][j]+=dp[i-1][k]*tmp.second;
                        }
                        else{
                            break;
                        }
                    }
                }
            }
            cout<<s[0];
            if(dp[sum][s[0].size()]!=0){
                printf(" can be formaed in ");
                write(dp[sum][s[0].size()]);
                puts(" weys");
            }
            else{
                puts(" is not a velid abbraviation");
            }
            s[0]=s[sum+1];
            sum=0;
        }
    }
    return 0;
}

附上几个样例。