题意分析

给定一组被忽略的不重要词和若干测试，每个测试包含一个大写缩写和一个由小写单词组成的短语。需计算在剔除不重要词后，将缩写字母按顺序分配给每个“重要词”中字母的不同方式数，且每个重要词至少匹配一个字母。

解题思路

1. 词过滤：先将短语拆成单词，去掉所有“不重要词”，得到待匹配的显著词序列 ${w_1,w_2,\dots,w_k}$。

2. 匹配处理：设缩写长度为 $m$，令 $T[1..m]$ 为缩写的小写形式。用一维数组 $\mathrm{dp}[j]=\text{已匹配前 }j\text{ 个缩写字母的方案数}.$

3. 逐词转移：初始 $\mathrm{dp}[0]=1,;\mathrm{dp}[j>0]=0$。对每个显著词 $w$（长度为 $L$），在词内再做一次“字符串子序列计数”：

   • 设临时数组 $\mathrm{ndp}[0..m]=\mathbf{0}$；
   • 遍历 $w[i],;i=1..L$，每遇到一个字符 $c=w[i]$，从 $j=m-1$ 到 $0$ 倒序： $\text{如果 }c=T[j+1]\text{，则 }\mathrm{ndp}[j+1]\mathrel{+}=\mathrm{dp}[j]\;+\;\mathrm{ndp}[j].$
   • 结束后令 $\mathrm{dp}\leftarrow\mathrm{ndp}$。 最后 $\mathrm{dp}[m]$ 即为答案。若为 $0$ 则说明无效。

本题代码

#include <iostream>
#include <string>
#include <vector>
#include <unordered_set>
#include <sstream>
#include <cmath>

using namespace std;
using ll = long long;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    while(true){
        int n;
        if(!(cin>>n) || n==0) break;
        unordered_set<string> insign;
        for(int i=0;i<n;i++){
            string s; cin>>s;
            insign.insert(s);
        }
        string line;
        getline(cin,line); // 读掉行尾
        while(getline(cin,line) && line!="LAST CASE"){
            if(line.empty()) continue;
            stringstream ss(line);
            string abbr;
            ss>>abbr;
            vector<string> words;
            string w;
            while(ss>>w){
                if(!insign.count(w)) words.push_back(w);
            }
            int m = abbr.size();
            string T = abbr;
            for(char &c:T) c = tolower(c);

            vector<ll> dp(m+1, 0);
            dp[0] = 1;

            // 对每个显著单词做子序列计数
            for(const auto &word: words){
                vector<ll> ndp(m+1, 0);
                for(char cw: word){
                    for(int j=m-1; j>=0; --j){
                        if(cw == T[j]){
                            ndp[j+1] += dp[j] + ndp[j];
                        }
                    }
                }
                dp.swap(ndp);
            }

            ll ans = dp[m];
            if(ans > 0)
                cout<<abbr<<" can be formed in "<<ans<<" ways\n";
            else
                cout<<abbr<<" is not a valid abbreviation\n";
        }
    }
    return 0;
}