题目大意：一个有一些单词组成的短语，给定一个缩写词，求此缩写由此短语的单词组成的可能方案数。注意，短语中所有重要的单词都要用到，顺序必须和缩写词单词顺序一致。
思路: dp。dp[i][j]代表缩写的前j个字母组成的缩写由前i个单词组成的可能方案数，则dp[i][j] = dp[i-1][j-1]W，W代表缩写的第j个字母在单词i出现的次数，但这样只求了主对角线的元素，每一个行的怎么办呢？其实有：dp[i][j+k] = dp[i-1][j-1]WW，WW代表j+k..M的缩写在单词i中出现的次数，而WW的求解可以参考两个字符串s1，s2，求s2作为s1的子串（连续的和不连续的）出现的次数求解。
实现: 一个很重要的是string从0开始，dp公式中dp[i-1][j-1]不好弄，所以统一用dp[i+1][j+k] = dp[i][j]WW来计算，也就是让dp[i+1][j+1]存dp[i][j}的值。另外边界值要注意：dp[0][0]=1，之所以这么设，因为求dp[1][1]=dp[0][0](缩写的第0个字母在单词0出现的次数)。
C++注意几点：
1、cin输入字符串时有空格会截断；
2、有空格的子串可以使用getline(cin, line)输入，但要注意略去前置\n，可以cin.ignore()，也可以getline(cin>>ws, line)。
3、一个句子中一个单词一个单词取可以使用istringstream。
代码:
//ACMAKER - ACM (ACronymMaker)
#include<iostream>
#include<sstream>
#include<cstring>
#include<algorithm>
#include<fstream>
#include<vector>
#include<set>
using namespace std;
#define MAXN 101
#define MAXM 160
string ignore[MAXN];
int n;
//dp[i][j]: 前i个单词中包含前j个缩写的个数
int dp[MAXM][MAXM];
//dp2[i][j]:
int dp2[MAXM][MAXM];
int main() {
for(;;) {
scanf("%d", &n);
if(n==0) break;
string s;
set<string> igs;
for(int i=0; i<n; i++) {
cin >> s;
igs.insert(s);
}
// ignore '\n'
cin.ignore();
for(;;) {
string line;
getline(cin, line);
if(line=="LAST CASE") break;
string abbr = line.substr(0, line.find(' '));
string t = line.substr(line.find(' ')+1);
vector<string> word;
istringstream ss(t);
do {
string w;
ss>>w;
if(w=="") break;
if(igs.find(w) == igs.end()) {
word.push_back(w);
}
}while(ss);
int n1 = word.size();
int n2 = abbr.length();
memset(dp, 0, sizeof(dp));
dp[0][0] = 1;
for(int i=0; i<n1; i++) {
for(int j=0; j<n2; j++) {
// 求第i个单词中含j..n2缩写的个数
memset(dp2, 0, sizeof(dp2));
int mx = min(n2-j, static_cast<int>(word[i].length()));
for(int p=0; p<=word[i].length(); p++) {
dp2[p][0] = 1;
}
for(int p=0; p<word[i].length(); p++) {
for(int q=0; q<mx; q++) {
dp2[p+1][q+1] = dp2[p][q+1];
if(tolower(word[i][p]) == tolower(abbr[j+q])) {
dp2[p+1][q+1] += dp2[p][q];
}
}
}
for(int k=1; k<=mx; k++){
dp[i+1][j+k] += dp[i][j]*dp2[word[i].length()][k];
}
}
}
/*
for(int i=0; i<=n1; i++) {
for(int j=0; j<=n2; j++) {
printf("(%d, %d) = %d\n", i, j, dp[i][j]);
}
}
*/
int ans = dp[n1][n2];
if(ans) {
cout << abbr << " can be formed in " << ans << " ways" << endl;
}else {
cout << abbr <<" is not a valid abbreviation" << endl;
}
}
}
return 0;
}
参考:
