題目鏈接：
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
【問(wèn)題概述】：給定一個(gè)長(zhǎng)度為N(n<=10)的由小寫字母組成的字符串，
如果該字符串左邊的字符都比右邊的字符的字典序大，則我們稱這個(gè)字符串是合法的，
否則不合法：
e.g: 字符串：abc ade 是合法的，而字符串：bac bca dae 則是不合法的。
現(xiàn)在對(duì)合法的字符串進(jìn)行如下的編碼（編號(hào)）：
a - 1
b - 2
...
z - 26
ab - 27
...
az - 51
bc - 52
...
vwxyz - 83681
...
我們的任務(wù)就是對(duì)于給定的字符串，如果她是合法的，則找到她的編號(hào)，否則不合法，輸出0：
【問(wèn)題分析】：首先想到的應(yīng)該是暴力，但是暴力的復(fù)雜度會(huì)達(dá)到O(10^26)，可能會(huì)超時(shí)，當(dāng)然有人爆過(guò)了。
這里將一個(gè)更為高效的算法。先看一下這個(gè)圖：
我們可以知道，長(zhǎng)度為k（k>=1)的字符串的編號(hào)是在長(zhǎng)度為k-1的基礎(chǔ)上增加而來(lái)的，為了計(jì)算的方便，我們可以先計(jì)算出長(zhǎng)度為k-1的字符串可以編號(hào)為多少，也就知道了長(zhǎng)度為k的第一個(gè)字符串的編號(hào)（加一就可以）。但是問(wèn)題還沒(méi)得到解決，下面是重點(diǎn)：該如何統(tǒng)計(jì)當(dāng)前輸入的長(zhǎng)度為k的字符串的編號(hào)：她等于長(zhǎng)度為k-1的最大編號(hào)加上當(dāng)前字符串在當(dāng)前長(zhǎng)度的編號(hào)。由此如何快速統(tǒng)計(jì)當(dāng)前字符串在當(dāng)前長(zhǎng)度的集合（把不同的長(zhǎng)度的字符串劃分為不同的集合）里編號(hào)是解決這個(gè)題目的第二個(gè)要點(diǎn)。
設(shè)s[k][i](0< i<= 26)表示長(zhǎng)度等于k的合法串以字母(i+'a'-1)開頭的串的數(shù)目，則規(guī)定s[k][26]表示長(zhǎng)度為k的集合的合法串的總的個(gè)數(shù)。對(duì)于給定的長(zhǎng)度為n的字符串，我們由右向左考慮，找第i個(gè)字符和第i-1個(gè)字符的關(guān)系：令tmp = s[ k ][ str[i] - 1] - s[k][ str[i-1] ]，表示在前i-1個(gè)字符不變時(shí)，可得到的不同的新合法字符串的個(gè)數(shù)。對(duì)于第一個(gè)字符，我們要判斷她是不是第一個(gè)字母‘a',不是的話，她可以得到的心合法字符串的個(gè)數(shù)為s[k][str[0]-1]. 最后的話，我們?cè)侔阉虚L(zhǎng)度小于n的字符長(zhǎng)的個(gè)數(shù)加起來(lái)就是我們要求的：下面是簡(jiǎn)單的代碼，供大家討論交流：
#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;
}