fzu1479 字符串编码

Problem 1479 字符串编码

Accept: 143    Submit: 513 Time Limit: 1000 mSec    Memory Limit : 32768 KB

Problem Description

在数据加密和数据压缩中常需要对特殊的字符串进行编码。给定的字母表A 由26 个小写英文字母组成A={a,b,…,z}。该字母表产生的升序字符串是指字符串中字母按照从左到右出现的次序与字母在字母表中出现的次序相同，且每个字符最多出现1 次。例如，a,b,ab,bc,xyz 等字符串都是升序字符串。现在对字母表A 产生的升序字符串按照字典序排列并编码如下。

1 a  2 b… 26 z  27 ab  28 ac…

对于一个升序字符串，迅速计算出它在上述字典中的编码。

Input

输入数据第一行有一个整数n。接下来n行每行有1个升序字符串

Output

按输入顺序每个升序字符串输出它的编码，每个编码占一行.

Sample Input

2 a ab

Sample Output

1 27

分析：

字符串长度为1:个数为 C(1, 26)

字符串长度为2: C(2, 26) ........字符串长度为26: C(26, 26);

所以总个数为：C(1, 26) + C(2, 26) + ...... + C(26, 26) = 2^26 - 1;

知道了这个、就看看代码：

#include <iostream> #include <cstdio> #include <cstring> using namespace std; int dp[30][30]; int C(int n, int m) { if (dp[n][m]) return dp[n][m]; if(m == n || n == 0) return dp[n][m] = 1; else return dp[n][m] = C(n, m-1) + C(n-1, m-1); } int main() { int T; char s[30]; memset(dp, 0, sizeof(dp)); scanf("%d", &T); while (T--) { scanf("%s", s); int len = strlen(s); int ans = 0; for (int i = 0; i < len; ++i) ans += C(i, 26); //长度小于len时所有的编号 char c = 'a'; for (int i = 0; i < len - 1; ++i) { while (c != s[i]) //长度为len时，s[i]前的所有编号 { int x = C(len - i - 1, 'z' - c); ans += x; ++c; } ++c; } ans += s[len - 1] - c; //计算长度小于len时所有的编号时已经加过1 printf("%d\n", ans); } return 0; } /** abcdefghijklmnopqrstuvwxyz **/