Code
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.
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.
• 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
之前写了几道数位dp的题目 改成了字母的就又不会了
其实思路也很简单，就是分成小于长度的和等于长度的两种情况
小于长度的情况直接排列组合就可以了 等于长度的情况从高位枚举
http://blog.csdn.net/lyy289065406/article/details/6648492 看了这篇博文 感觉很好理解
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<queue>
using namespace std;
int c[30][30];
char str[12];
void Cmn()
{
c[0][0] = 1;
for(int i = 1; i < 30; i++){
c[i][0] = c[i][i] = 1;
for(int j = 1;j < i; j++){
c[i][j] = c[i - 1][j] + c[i - 1][j - 1];
}
}
}
void solve()
{
int sum = 0;
for(int i = 1; i < strlen(str); i++){
sum += c[26][i];
}
for(int i = 0; i < strlen(str); i++){
char ch = (!i)?'a':str[i - 1] + 1;
while(ch <= str[i] - 1){
sum += c['z' - ch][strlen(str) - i - 1];
ch++;
}
}
sum ++;
cout<<sum <<endl;
}
int main()
{
Cmn();
cin>> str;
for(int i = 1; i < strlen(str); i++){
if(str[i] <= str[i - 1]){
cout<< 0<<endl;
return 0;
}
}
solve();
return 0;
}