POJ 1850 - Code

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

POJ 1496 - Word Index と全く同じ問題なので略．

 1 #include <iostream>
 2 using namespace std;
 3 
 4 int comb[27][27];
 5 
 6 int encode(const string& s)
 7 {
 8   const int len = s.size();
 9   int r = 0;
10   for (int i = 0; i < len; i++) {
11     if (s[i-1] < s[i]) {
12       r = r + comb[26][i+1] - comb[26-(s[i]-'a'+1)][len-i];
13     } else {
14       return 0;
15     }
16   }
17   return r;
18 }
19 
20 int main()
21 {
22   for (int i = 0; i <= 26; i++) {
23     comb[i][0] = 1;
24     comb[i][i] = 1;
25   }
26   for (int n = 1; n <= 26; n++) {
27     for (int k = 1; k < n; k++) {
28       comb[n][k] = comb[n-1][k] + comb[n-1][k-1];
29     }
30   }
31 
32   string s;
33   while (cin >> s) {
34     cout << encode(s) << endl;
35   }
36 
37   return 0;
38 }