POJ 1850 Code 組合數 編碼

題意：

輸出某個str字元串在字典中的位置。

規定長度小的字元串排在長度大的字元串前面，并且輸入的字元串的字元必須是升序排列。不降序列是非法字元串。

由于字典是從a=1開始的，是以str的位置值就是 在str前面所有字元串的個數 +1

對于輸入的英文字元串：

1.先判斷是否合法，即是否能進行code

2.然後就是要求  編碼小于它的個數+1

3.先計算長度小于該字元串的編碼數量

假如輸入字元串長度為L

那麼對于長度len的字元串(1<=len<L)

有C[26][len]個可編碼，

因為就是從26個字母裡面選出len個不同的字母，然後按照字母順序有唯一一種排列。

4.然後計算長度等于該字元串，但是字典序小于它的字元串。

對字元串從左往右掃描，假若目前位置字母為'y',上一位的字母為'b' ，

枚舉目前位為'c','d','e','f'...'x'的情況(保證了字典序比自己小,并且合法)。對未掃描的位置進行排列組合。

見代碼。

5.+1(因為要給自己編号，還要加自身)

Code

Time Limit: 1000MS	Memory Limit: 30000K
Total Submissions: 9226	Accepted: 4399

Description

Transmitting and memorizing information is a task that requires different coding systems for the best use of the available space. A well known system is that one where a number is associated to a character sequence. It is considered that the words are made only of small characters of the English alphabet a,b,c, ..., z (26 characters). From all these words we consider only those whose letters are in lexigraphical order (each character is smaller than the next character). 

The coding system works like this: 

• The words are arranged in the increasing order of their length. 

• The words with the same length are arranged in lexicographical order (the order from the dictionary). 

• We codify these words by their numbering, starting with a, as follows: 

a - 1 

b - 2 

... 

z - 26 

ab - 27 

... 

az - 51 

bc - 52 

... 

vwxyz - 83681 

... 

Specify for a given word if it can be codified according to this coding system. For the affirmative case specify its code. 

Input

The only line contains a word. There are some constraints: 

• The word is maximum 10 letters length 

• The English alphabet has 26 characters. 

Output

The output will contain the code of the given word, or 0 if the word can not be codified.

Sample Input

bf      

Sample Output

55      

Source

Romania OI 2002

#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<vector>
#include<iomanip>
using namespace std;

#define all(x) (x).begin(), (x).end()
#define for0(a, n) for (int (a) = 0; (a) < (n); (a)++)
#define for1(a, n) for (int (a) = 1; (a) <= (n); (a)++)
typedef long long ll;
typedef pair<int, int> pii;
const int INF =0x3f3f3f3f;
const int maxn=26    ;
ll ret,C[maxn+3][maxn+3];
int n;
char s[15];
void pre()//打表，楊輝三角,組合數
{
    C[0][0]=1;
    for(int i=1;i<=maxn;i++)
    {
        C[i][0]=C[i][i]=1;
        for(int j=1;j<i;j++)
        {
            C[i][j]=C[i-1][j-1]+C[i-1][j];
        }
    }
}

bool check()//判斷是否合法，即是否能進行code
{
    for1(i,n-1)
    {
        if(s[i]>=s[i+1]) return false;
    }
    return true;
}
ll work()
{
    ll ans=0;
    for1(i,n-1)//先計算長度小于該字元串的編碼數量
    {
        ans+=C[26][i];
    }
    for1(i,n)
    {
        int ind=s[i]-'a'+1;
        int st= i==1?1:s[i-1]-'a'+1+1;//這一位至少要比前一位大
        for(int j=st;j<=ind-1;j++)//枚舉這一位
        {
            if(n-i>26-j)  continue;
            ans+=C[26-j][n-i];
        }
    }
    ans++;
    return ans;
}
int main()
{
    pre();
   while(~scanf("%s",s+1))
   {
       n=strlen(s+1);
       if(!check())  {puts("0");continue;}
       printf("%lld\n",work());
   }


   return 0;
}