题解 P1246 【编码】

本题本质上是一个找规律填表(暨递推)的题目 思路非常明确，举一个简单的例子： ------------ 对于一个字符串“ade”，它的长度为3. 那么他在题设要求中的字符串编号可以用以下方式求解： 1. 所有**长度为1和2**的字符串数量 + 所有**开头为a**，**由bc到de**的字符串数量； 2. 所有开头为a，由bc到de的字符串数量就相当于所有**开头为d长度为2**的字符串数量加上**开头为d长度为2直到末位是e**的字符串数量； ------------ 由以上例子第二条我们可以类比其他情况，得到这样一个表格 [得到的表格](https://imgchr.com/i/PeVi9K) **~~P.S.你可以在Excel中很轻松地制作出这个表格~~** 在该表格中，横行表示开头字母，纵行表示字串长度，表格中的数据以该字母开头的该长度字符串的总数 对于任何一群以i开头，长度为j的字符串，它的数量均为可以以这样一个公式表示： ## $f[i][j] = f[i + 1][j - 1] + f[i + 2][j - 1] + f[i + 3][j - 1] + … + f[z][j - 1]$ 如果无法理解，没关系，我们再举一个例子 ------------ 以a开头，长度为3的字符串数量如何计算？ 这样的字符串有很多： abc acd ace ... 我们可以发现，这样的字符串的数量就相当于以b开头的长度为2的串的数量，加上以c开头长度为2的串的数量...一直到以y开头长度为2的串的数量，即为以上公式 **（由于题设要求，没有以z开头长度为2的合法串）** ------------ 但这样一个公式计算起来仍不方便，别急，我们再来看 由上面的公式，用i + 1替换i,我们可以得到这样一个式子 ## $f[i + 1][j] = f[i + 2][j - 1] + f[i + 3][j - 1] +…+f[z][j - 1]$ 将这个式子带入刚刚的公式，就可以得到表格的计算方法： ## $f[i][j] = f[i + 1][j - 1] + f[i + 1][j]$ 用程序运行这个公式，计算数组f[i][j]，就可以得到上述表格 而显然地，计算某个字符串的编号，就是计算字符串每一位在对应行从a到该位的值得和，说的比较抽象，举个例子就能理解 ------------ 对于一个字符串“ade”： 从右至左，第一位是1，则第一行将a-e的数值相加 第二位是d，将第二行a-d的数值相加 以此类推，得到最终答案399. ------------ 至此，本题思路已分析完毕，接下来就是代码实现，需要注意一些细节的处理（数组下标一类），以下是完整代码 ``` #include<iostream> using namespace std; string s; int f[30][10],ans,cnt; int main(){ cin >> s; for(int i = 1;i < s.size();i++){ if(s[i - 1] >= s[i]){ cout << 0; return 0; } } //判断字符串是否合法（升序） for(int i = 1;i <= 26;i++) f[i][1] = 1; //长度为1的字符串数量都是1 for(int j = 2;j <= 6;j++) for(int i = 27 - j;i > 0;i--) f[i][j] = f[i + 1][j - 1] + f[i + 1][j]; //由公式，我们从上至下从右至左进行计算 for(int j = s.size() - 1;j >= 0;j--){ cnt++; for(int i = 1;i <= s[j] - 'a' + 1;i++) ans += f[i][cnt]; } //由以上的思路计算答案 cout << ans; return 0; } ```