题解：SP1703 ACMAKER - ACM (ACronymMaker)

题目大意：

一个有一些单词组成的短语，给定一个缩写词，求此缩写由此短语的单词组成的可能方案数。注意，短语中所有重要的单词都要用到，顺序必须和缩写词单词顺序一致。

思路

动态规划设置：

• \(dp_{i,j}\)：使用前 \(i\) 个重要单词形成前 \(j\) 个缩写字符的方法数。
• \(dp2_{k,m}\)：辅助数组，用于帮助转移，其中 \(k\) 索引当前单词的字符，\(m\) 索引缩写的字符。

转移方程

\(dp2\) 数组转移：

• \(dp2_{k+1,m+1}\gets dp2{k,m+1}\) 处理当前单词字符不用于匹配当前缩写字符的情况。
• \(dp2_{k+1,m+1}\gets dp2_{k+1,m+1}+dp2_{k,m}\)，处理当前单词字符匹配当前缩写字符的情况。

\(dp\) 数组转移：

• \(dp_{i+1,j+k}\gets dp{i+1,j+k}+dp_{i,j} \cdot dp2_{size,k}\)，考虑使用当前单词匹配缩写的所有方式。

代码：

#include<bits/stdc++.h>
#define wrhlovezcx true
using namespace std;
int main(){
	while(wrhlovezcx){
		int n;
		cin>>n;
		if(n==0) return 0;
		set<string> ig;
		for(int i=0;i<n;i++){
			string s;
			cin>>s;
			ig.insert(s);
		}
		while(wrhlovezcx){
			string acm;
			cin>>acm;
			cin.ignore();
			string phrase;
			getline(cin,phrase);
			if(phrase=="CASE") break;
			istringstream iss(phrase);
			vector<string> words;
			while(wrhlovezcx){
				string word;
				iss>>word;
				if(word=="") break;
				if(ig.find(word)==ig.end()){
					words.push_back(word);
				}
			}
			int dp[151][151];
			memset(dp,0,sizeof(dp));
			dp[0][0]=1;
			int dp2[151][151];
			for(int i=0;i<words.size();i++){
				for(int j=0;j<acm.length();j++){
					int mx=min(acm.length()-j,words[i].length());
					for(int k=0;k<=words[i].length();k++){
						dp2[k][0]=1;
					}
					for(int k=1;k<=mx;k++){
						dp2[0][k]=0;
					}
					for(int k=0;k<words[i].length();k++){
						for(int m=0;m<mx;m++){
							dp2[k+1][m+1]=dp2[k][m+1];
							if(words[i][k]==tolower(acm[j+m])){
								dp2[k+1][m+1] += dp2[k][m];
							}
						}
					}
					for(int k=1;k<=mx;k++){
						dp[i+1][j+k]+=dp[i][j]*dp2[words[i].length()][k];
					}
				}
			}
			if(dp[words.size()][acm.length()]==0){
				cout<<acm<<" is not a valid abbreviation"<<endl;
			}else{
				cout<<acm<<" can be formed in "<<dp[words.size()][acm.length()]<<" ways"<<endl;
			}
		}
	}
}