pku1850 code 求字符串的位置，DP

給出一個字符串的序
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
...
然后給出一個字符串，要求求在字典中的位置。
設狀態dp[l][p]為長度為l的字符串且以p為字母開頭的個數為多少。
dp[l][p]=sum{dp[l-1][i]} i>k
下面就不用解釋了吧- -

 1# include <cstdio>
 2# include <iostream>
 3# include <cstring>
 4using namespace std;
 5int dp[11][26];
 6int main()
 7{
 8    memset(dp,0,sizeof(dp));
 9    for(int i=0;i<26;i++)
10      dp[1][i]=1;
11    for(int len=2;len<=10;len++)
12        for(int i=0;i<26;i++)
13          for(int j=i+1;j<26;j++)
14            dp[len][i]+=dp[len-1][j];
15   char str[100];
16   scanf("%s",str);
17   for(int i=1;i<strlen(str);i++)
18     if(str[i]<=str[i-1])
19     {
20        printf("0\n");
21        return 0;
22     }
23   int total=0;
24   for(int len=0;len<strlen(str);len++)
25     for(int i=0;i<26;i++)
26       total+=dp[len][i];
27   int last=0;
28   for(int i=0;i<strlen(str);i++)
29   {
30     for(int j=last;j<str[i]-'a';j++)
31       total+=dp[strlen(str)-i][j];
32     last=str[i]-'a'+1;
33   }
34   printf("%d\n",total+1);
35   //system("pause");
36   return 0;
37    
38}
39

posted on 2010-10-28 00:58 yzhw 閱讀(106) 評論(0)  編輯 收藏 引用 所屬分類: DP