POJ 2731 - ACM(ACronymMaker)

http://poj.org/problem?id=2731

概要

大文字のアルファベットからなる略語と、小文字のアルファベットからなるいくつかの単語が与えられる。 与えられた略語になるような選び方が何通りあるか答える。

\(n\) 個の重要でない単語が与えられ、それに含まれる単語から略語となるアルファベットを選んではならない。 また、各単語から1つ以上のアルファベットを選ばなければならない。 もちろん、選んだアルファベットは略語と同じ順番に現れなければならない。

制約

解法

まず重要でない単語は最初から除外して考えればいい。

dp[i][j] = i 番目までの単語で略語の j 文字目までを作る選び方

という DP。 i 番目の単語で初めて j 文字目を作るには以下の2種類しかない。

 1 #include <iostream>
 2 #include <sstream>
 3 #include <vector>
 4 #include <set>
 5 #include <cctype>
 6 #include <algorithm>
 7 using namespace std;
 8 
 9 long long solve(const string& abbr, const vector<string>& words)
10 {
11   static long long dp[200][200];
12   const int N = words.size(), M = abbr.size();
13   for (int i = 0; i < N; i++) {
14     fill_n(dp[i], M, 0);
15   }
16   for (string::const_iterator it = words[0].begin(); it != words[0].end(); ++it) {
17     for (int j = M-1; j >= 0; j--) {
18       if (*it == abbr[j]) {
19         if (j == 0) {
20           ++dp[0][j];
21         } else {
22           dp[0][j] += dp[0][j-1];
23         }
24       }
25     }
26   }
27   for (int i = 1; i < N; i++) {
28     const string& s = words[i];
29     for (string::const_iterator it = s.begin(); it != s.end(); ++it) {
30       for (int j = M-1; j >= i; j--) {
31         if (*it == abbr[j]) {
32           dp[i][j] += dp[i-1][j-1] + dp[i][j-1];
33         }
34       }
35     }
36   }
37   return dp[N-1][M-1];
38 }
39 
40 int main()
41 {
42   ios::sync_with_stdio(false);
43   int N;
44   while (cin >> N && N != 0) {
45     set<string> ignore;
46     for (int i = 0; i < N; i++) {
47       string s;
48       cin >> s;
49       ignore.insert(s);
50     }
51     cin.ignore();
52     for (string s; getline(cin, s) && s != "LAST CASE";) {
53       istringstream iss(s);
54       string t;
55       iss >> t;
56       vector<string> words;
57       while (iss >> s) {
58         if (!ignore.count(s)) {
59           words.push_back(s);
60         }
61       }
62       cout << t << " ";
63       for (string::iterator it = t.begin(); it != t.end(); ++it) {
64         *it = tolower(*it);
65       }
66       long long ans = solve(t, words);
67       if (ans == 0) {
68         cout << "is not a valid abbreviation" << endl;
69       } else {
70         cout << "can be formed in " << ans << " ways" << endl;
71       }
72     }
73   }
74   return 0;
75 }
poj/2731.cc