编码

Problem description

编码工作常被运用于密文或压缩传输。这里我们用一种最简单的编码方式进行编码：把一些有规律的单词编成数宇。
字母表中共有26个字母{a，b，…，z}，这些特殊的单词长度不超过6且字母按升序排列。把所有这样的单词放在一起，按字典顺序排列，一个单词的编码就对应着它在字典中的位置。
　　例如：
　　a→1
　　b→2
　　……
　　z→26
　　ab→27
　　ac→28
　　……
你的任务就是对于所给的单词，求出它的编码。

Input format　

仅一行，被编码的单词。

Output format

仅一行，对应的编码。如果单词不在字母表中，输出0。

Algorithm design

模拟AC/动态规划AC

Problem analysis

模拟AC

先敲一下暴力，方便对拍

模拟的思路很好想，将字母转化为数字，进行类似26进制的依次加法

（发现好像直接用字母处理更方便..）

但26进制应该z过了之后是aa这样，所以还是有所不同

无论如何，到底只是一个简单的维护单调序列的问题

每次从后往前枚举，找到第1个可以进的数字，加1

同时将其后所有数字变为从它开始的单调递增1序列

（如果是26进制则应该将之后所有数字变为a）

当然在找数字的时候也要注意保证修改后不会有数超过z

如果找不到这样的数字，那么加1位，从头开始abc…

每次将得到的结果与目标进行比对即可

至于不在字母表中，直接在开头判断，出现非单调性，或者不在a~z就输0

复杂度不高，O(26个数中长度不大于6的有序区间的个数*6)，不会算…

可以过，但是数据模拟到6位的时候，程序会爆掉，不知道为什么

动态规划AC

在随手画画的过程中发现

以字母j开头的长为i的字母的总数是一个可以算出的值

比如说，3,w就是3,x+2,x，其他的以此类推

Opt[i][j]=opt[i][j+1]+opt[i-1][j+1]

为什么呢

在同一长度下，i总是包括i+1的所有情况（只是开头字母换了）

又因为i比i+1少1，所以第二个字母又比i+1的第二个字母多1种情况

故在第二个字母为i+1时，opt[i][j]又有一个opt[i-1][j+1]

那么所有的opt[i][j]都是能算出来的

接着就是数学处理了

为了方便，先将小于所给单词的所有情况都加上

然后每次取出位数相同，首数却小于自身的情况，再删去自己的首数继续

这里有个难点，每次开始枚举的起点，都应该是上一次的首数+1

其他没什么了

Source code

#include <bits/stdc++.h>

using namespace std;

struct node
{
    int num[7];
    int len;
}ans,key;//定义结构体，存储数字和规格
string st;

void input()
{
    freopen("test.in","r",stdin);
    freopen("test.out","w",stdout);
    cin>>st;
    memset(key.num,0,sizeof(key.num));
    memset(ans.num,0,sizeof(ans.num));
    key.len=1;
    key.num[1]=1;
    ans.len=st.size();
    for(int i=1;i<=ans.len;i++)
        ans.num[i]=st[i-1]-'a'+1;
//将答案保存入结构体
    return ;
}

void operate(node now,int turn)
{
    if(now.len==ans.len)
    {
        bool flag=true;
        for(int i=1;i<=now.len;i++)
            if(now.num[i]!=ans.num[i])
            {
                flag=false;
                break;
            }
        if(flag)
        {
            cout<<turn<<endl;
            return;
        }
    }//满足答案即输出
    for(int i=now.len;i>=1;i--)
        if(now.num[i]+now.len-i<26)
        {
            now.num[i]++;
            for(int j=i+1;j<=now.len;j++)
                now.num[j]=now.num[j-1]+1;
            operate(now,turn+1);
            return ;
        }
    now.len++;
    for(int i=1;i<=now.len;i++)
        now.num[i]=i;
    operate(now,turn+1);
//和Analysis说的一样了
    return ;
}

int main()
{
    input();
    for(int i=1;i<=ans.len;i++)
        if((i>1&&ans.num[i]<=ans.num[i-1])||ans.num[i]>26||ans.num[i]<1)
        {
            cout<<"0"<<endl;
            return 0;
        }
//直接判断是否不符合
    operate(key,1);
    return 0;
}

#include <bits/stdc++.h>

using namespace std;

int cnt[10][30],ans,len;
//cnt[i][j]表以i开头的j位数有多少个
string st;

void input()
{
    freopen("test.in","r",stdin);
    freopen("test.out","w",stdout);
    cin>>st;
    len=st.size();
    return ;
}

void pretreatment()
{
    memset(cnt,0,sizeof(cnt));
    for(int i=1;i<=26;i++)
        cnt[1][i]=1;
    //1位的任何字母都只有一种
    for(int i=2;i<=6;i++)
        for(int j=26-i+1;j>=1;j--)
            cnt[i][j]=cnt[i][j+1]+cnt[i-1][j+1];
    //从当前位数下可以采用的最大数首开始递减，如：w,3比x,3多了x,2种情况
    return ;
}

void operate()
{
    ans=1;
    for(int i=1;i<len;i++)
        for(int j=1;j<=26-i+1;j++)
            ans+=cnt[i][j];
    //先把比自己位数小的算上，可以用前缀和优化，但是可以过就不费事了
    int wei=1;
    while(len)
    {
        for(int i=wei;i<st[0]-'a'+1;i++)
            ans+=cnt[len][i];
        //把同位数中低于自己的算上
        wei=st[0]-'a'+2;
        st=st.substr(1);
        len--;
    }
    return ;
}

int main()
{
    input();
    for(int i=0;i<len;i++)
        if((i>0&&st[i]<=st[i-1])||st[i]>'z'||st[i]<'a')
        {
            cout<<"0"<<endl;
            return 0;
        }
    //先判断是不是符合单词
    pretreatment();
    operate();
    cout<<ans<<endl;
    return 0;
}

over