首页 > 代码库 > POJ1850 组合数学
POJ1850 组合数学
POJ1850
问题重述:
用26个小写字母进行编码,编码规则如下:
1)每个编码中前一个字母必须小于后一个字母
2)编码按照长度从小到大排列,相同长度按字典序进行排列
输入一个字母串,求解该编码对应的数值。
问题分析:
该问题等价于求解小于输入编码的编码的数目。
对于编码X = x1,x2,x3,...xk, 小于X的编码可以分为两个部分
1)位数小于k的编码。
这部分编码的数目 = C[26][1] + C[26][1] + ... + C[26][k - 1]
2)长度为k,且小于X的编码。
假设Y为满足该条件的编码,现只需确定Y的数目。从左到右遍历编码X: i = 1 to k,假设X和Y的前i - 1位均相等且 yi != xi,那么 yi 必须满足 xi-1 = yi - 1 < yi < xi。
对于yi的每一种取值, yi, yi + 1, ... yk只需满足递增关系即可, 共有C[26][25 - (yi - ‘a‘)]种编码。
根据以上分析,即可求出结果。
AC代码:
1 //Memory: 204K Time: 0MS 2 #include <iostream> 3 #include <cstdio> 4 #include <cstring> 5 #include <string> 6 #include <algorithm> 7 8 using namespace std; 9 10 string s, ss;11 int c[27][27];12 13 void init()14 {15 for (int i = 0; i <= 26; i++) 16 c[i][0] = c[i][i] = 1;17 18 for (int i = 1; i <= 26; i++)19 for (int j = 0; j < i; j++)20 c[i][j] = c[i - 1][j] + c[i - 1][j - 1];21 }22 23 int main()24 {25 cin >> s;26 27 int len = s.size();28 for (int i = 0; i < len - 1; i++) {29 if (s[i] > s[i + 1] || s[i] == s[i + 1]){30 cout << 0 << endl;31 return 0;32 }33 }34 35 init();36 int ans = 0;37 for (int i = 1; i <= len - 1; i++) {38 ans += c[26][i];39 }40 41 for (int i = 0; i < s[0] - ‘a‘; i++) {42 ans += c[25 - i][len - 1];43 }44 45 for (int i = 1; i < len; i++) {46 for (int j = s[i - 1] - ‘a‘ + 1; j < s[i] - ‘a‘; j++)47 ans += c[25 - j][len -1 - i];48 }49 cout << ans + 1 << endl;50 51 return 0;52 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。