POJ1850 Code-动态规划

发表于 | 分类于 | 浏览 次
字数统计: 1,208 | 阅读时长 ≈ 6

题目

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.

input

The only line contains a word. There are some constraints:

  • 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

output: 55

问题陈述

按照题目给出的例子，给出字母串表标号。

题目中给出的字母串中字母是“单调递增”的，也就是没有重复，后一个要大于前一个

思路

所谓“标号”，就是某一个字母串前面的字母串个数+1

问题转化为求字母串前面的字母串个数

某一个字母串前面的字母串有三种情况:

  1. 长度小于该字母串
  2. 长度等于该字母串，首字母小于该字母串首字母
  3. 长度和首字母都与该字母串相等，但位置更靠前

因为后面的字母串对前面的字母串有包含的关系，所以考虑用动态规划来求解，那接下来的重点就是寻找状态转移方程了

用$dp[i][j]$表示长度为$i$首字母为$j$的字母串个数，那么$dp[i+1][j]=dp[i][j+1]+dp[i][j+2]+···+dp[i][‘z’-i]$

光看公式可能理解得不是很好，举个例子吧：
比如我们现在想求长度是5位，b打头的字母串的个数:

b _ _ _ _ ······$dp[5][b]$

那么考虑后面的四位，有下面的22种情况：

b ++c++ _ _ _ ······$dp[4][c]$

b ++d++ _ _ _ ······$dp[4][d]$

b ++e++ _ _ _ ······$dp[4][e]$

···

b ++w++ ++x++ ++y++ ++z++ ······$dp[4][w]$

把上面的22种情况相加，就可以得到长度为5，b打头的所有字母串个数$p[5][b]$

对于其中的$dp[4][j]$也应用上述的方法可以求解

有了上面的思路，就可以由最初的$dp[1][j]=1$逐步求出完整的$dp[i][j]$表了！

好开心是不是，下面算个题试试好不好用吧：

假如我们现在要求字母串“cefkq”的序号，也就是这个字母串前面有多少个。回头看那三种情况：

  1. 长度小于该字母串 —— 把所有的$dp[4][j]$，$dp[3][j]$，$dp[2][j]$，$dp[1][j]$加起来
  2. 长度等于该字母串，首字母小于该字母串首字母 —— $dp[5][a]$,$dp[5][b]$加起来
  3. 长度和首字母都与该字母串相等，但位置更靠前

嗯，问题解决了一大部分了，现在就剩第三种情况了！！！！
再看一眼字母串“cefkq”

长度和首字母都相等，位置比它在前面，那就一位一位考虑呗

第二位是e，
c ++d++ _ _ _在它前面！所以又有$dp[4][d]$个在它前面的，加上！

第三位是f，ef中间没有其他字母了，继续往后看

第四位是k，fk中间还有g、h、i、j

c e ++g++ _ _ ······$dp[3][g]$

c e ++h++ _ _ ······$dp[3][h]$

c e ++i++ _ _ ······$dp[3][i]$

c e ++j++ _ _ ······$dp[3][j]$

统统加上！

······

再往后就跟前面一样了，不再赘述了

到这，问题解决了，上代码

代码

#include "stdafx.h"
#include "iostream";
#include <string>
using namespace std;
int main() {
    string str;
    cin >> str;
    int len = str.length();
    int result = 1;
    if (len>10){
        result= 0;
    }
    if ((str[0]-'a')<0 || (str[0] - 'a')>25){
        result= 0;
    }
    //初始化dp表
    int dp[10][26] = { 0 };
    for (int i = 0; i < 26; i++) {
        dp[0][i] = 1;
    }
    for (int i = 1; i < 10; i++) {
        for(int j = 0; j < 26-i; j++) {
            for (int k = j + 1; k < 27-i; k++) {
                dp[i][j] += dp[i-1][k];
            }
        }
    }
    //dp表每一行总数，也就是长度为k的字母串总数
    int sum[10] = { 0 };
    for (int i = 0; i < 10; i++) {
        for (int j = 0; j < 26 - i; j++) {
            sum[i] += dp[i][j];
        }
    }
    
    
    int temp = len-2;
    //位数小于n的数的个数
    for (int i = 0; i < len-1; i++){
        result += sum[i];
    }
    //位数=n但首字母比n首字母小的个数
    for (int i = 0; i < str[0]-'a'; i++) {
        result += dp[len-1][i];
    }
    //位数=n但中间字母比n小的个数
    for (int i = 1; i < len; i++) {
        int left = str[i-1] - 'a';
        int now = str[i] - 'a';
        if (now<0|| now>25){
            result =  0;
        }
        if (now <= left){
            result = 0;
        }
        for (int j = left+1; j < now; j++){
            result += dp[temp][j];
        }
        temp--;
    }
    cout << result;
    return result;
}