題目鏈接：
pku_1850_Code_ http://162.105.81.212/JudgeOnline/problem?id=1850
pku_1496_Word Index http://162.105.81.212/JudgeOnline/problem?id=1496
【問題概述】：給定一個長度為N(n<=10)的由小寫字母組成的字符串，
如果該字符串左邊的字符都比右邊的字符的字典序大，則我們稱這個字符串是合法的，
否則不合法：
e.g: 字符串：abc ade 是合法的，而字符串：bac bca dae 則是不合法的。
現(xiàn)在對合法的字符串進行如下的編碼（編號）：
a - 1
b - 2
...
z - 26
ab - 27
...
az - 51
bc - 52
...
vwxyz - 83681
...
我們的任務(wù)就是對于給定的字符串，如果她是合法的，則找到她的編號，否則不合法，輸出0：
【問題分析】：首先想到的應(yīng)該是暴力，但是暴力的復(fù)雜度會達到O(10^26)，可能會超時，當然有人爆過了。
這里將一個更為高效的算法。先看一下這個圖：
我們可以知道，長度為k（k>=1)的字符串的編號是在長度為k-1的基礎(chǔ)上增加而來的，為了計算的方便，我們可以先計算出長度為k-1的字符串可以編號為多少，也就知道了長度為k的第一個字符串的編號（加一就可以）。但是問題還沒得到解決，下面是重點：該如何統(tǒng)計當前輸入的長度為k的字符串的編號：她等于長度為k-1的最大編號加上當前字符串在當前長度的編號。由此如何快速統(tǒng)計當前字符串在當前長度的集合（把不同的長度的字符串劃分為不同的集合）里編號是解決這個題目的第二個要點。
設(shè)s[k][i](0< i<= 26)表示長度等于k的合法串以字母(i+'a'-1)開頭的串的數(shù)目，則規(guī)定s[k][26]表示長度為k的集合的合法串的總的個數(shù)。對于給定的長度為n的字符串，我們由右向左考慮，找第i個字符和第i-1個字符的關(guān)系：令tmp = s[ k ][ str[i] - 1] - s[k][ str[i-1] ]，表示在前i-1個字符不變時，可得到的不同的新合法字符串的個數(shù)。對于第一個字符，我們要判斷她是不是第一個字母‘a',不是的話，她可以得到的心合法字符串的個數(shù)為s[k][str[0]-1]. 最后的話，我們再把所有長度小于n的字符長的個數(shù)加起來就是我們要求的：下面是簡單的代碼，供大家討論交流：
#include <iostream>
#include <string.h>
using namespace std;
const int maxn = 28;
int s[11][maxn], n;
bool isValid(char *s, int &n) {
int i = n = 0;
for(i = 1; s[i]; i++)
if(s[i] <= s[i-1]) return 0;
n = i;
return 1;
}
void init() {
s[0][27] = 1;
for (int k = 1; k < 11; k++) {
int m = 26-k+1;
for (int i = 1; i <= m; i++) {
s[k][i] += s[k][i-1] + s[k-1][m+1]-s[k-1][i];
}
}
s[0][27] = 0;
}
void pt() {
int sum = 0;
for (int k = 1; k < 11; k++) {
int m = 26-k+1;
for (int i = 1; i <= m; i++) {
printf("s[%d][%d] = %d\n", k, i, s[k][i]);
}
sum += s[k][m];
}
printf("%d\n", sum);
}
inline int d(char c) { return c-'a'+1;}
int main() {//freopen("in.in", "r", stdin);
init(); //pt();
char str[11];
int m, i, k;
while(scanf("%s", str) != EOF) {
if (!isValid(str, n)) { puts("0"); continue;}
for (i = n-1, k = 1, m = 1; i >= 1; i--, k++)
m += s[k][d(str[i]-1)] - s[k][d(str[i-1])];
if (str[0] != 'a') m += s[k][d(str[0]-1)];
for (i = 1; i < k; i++) m += s[i][26-i+1];
printf("%d\n", m);
}
return 0;
}