蓝桥杯 算法训练 Cowboys DP

算法训练 Cowboys  

时间限制：2.0s   内存限制：256.0MB

问题描述

　　一个间不容发的时刻：n个牛仔站立于一个环中，并且每个牛仔都用左轮手枪指着他旁边的人！每个牛仔指着他顺时针或者逆时针方向上的相邻的人。正如很多西部片那样，在这一刻，绳命是入刺的不可惜……对峙的场景每秒都在变化。每秒钟牛仔们都会分析局势，当一对相邻的牛仔发现他们正在互指的时候，就会转过身。一秒内每对这样的牛仔都会转身。所有的转身都同时在一瞬间发生。我们用字母来表示牛仔所指的方向。“A”表示顺时针方向，“B”表示逆时针方向。如此，一个仅含“A”“B”的字符串便用来表示这个由牛仔构成的环。这是由第一个指着顺时针方向的牛仔做出的记录。例如，牛仔环“ABBBABBBA”在一秒后会变成“BABBBABBA”；而牛仔环“BABBA”会变成“ABABB”。 这幅图说明了“BABBA”怎么变成“ABABB” 一秒过去了，现在用字符串s来表示牛仔们的排列。你的任务是求出一秒前有多少种可能的排列。如果某个排列中一个牛仔指向顺时针，而在另一个排列中他指向逆时针，那么这两个排列就是不同的。

输入格式

　　输入数据包括一个字符串s，它只含有“A”和“B”。

输出格式

　　输出你求出来的一秒前的可能排列数。

数据规模和约定

　　s的长度为3到100（包含3和100）

样例输入

BABBBABBA

样例输出

2

样例输入

ABABB

样例输出

2

样例输入

ABABAB

样例输出

4

样例说明

　　测试样例一中，可能的初始排列为："ABBBABBAB"和 "ABBBABBBA"。

　　测试样例二中，可能的初始排列为："AABBB"和"BABBA"。

    根据题目，我们可以将A看作往右看，B看作往左看。再进一步，我们可以说AB并列的情况就要转化为BA，其余情况不用考虑。

    而题目中说这些牛仔是站成了一个环而不是一条线，所以我们还要注意首尾是否需要转化的问题。那么我们要进行查找，首先要确定一个起点，我们这里在这个字符串中找出第一个BA存在的位置，然后假设这个BA是通过AB转化而来的，之后不再考虑这个BA，将BA后一位当作起点，BA前一位当作终点。然后再处理一遍假设这个BA原来就是BA没变的情况，这两个情况相加起来就能得到最后的结果。

    这里用DP的方式，建立一个数组dp[i][j]，i表示当前所在的点，j表示这个状态是否发生了变化（变化了为1，未变化为0），这个数组就表示在这个情况时一秒前牛仔站位的所有可能性。为了确定有多少可能性，我们将这一位的字母与前一位的字母比较，然后进行分类讨论。

    起点因为只有一个字母，所以不会发生变化，初始化dp[st][0]=1,dp[st][1]=0。

①当前为B，前者为A（AB）

    如果这两位为AB，那么只存在一种可能，之前是ABB，然后得到了AAB（也可能是AAB→ABA，但是这样就相当于后面B和前面的A发生的状态变化，所以这里不考虑。）所以如果是AB，我们可以说B是一定不会发生变化的，即dp[st][1]=0。而发生变化有多少种情况取决于前面的A变化有多少种情况，所以dp[st][0]=dp[st-1][1]。

②当前为A，前者为B（BA）

    如果这两位为BA，那么可能是由AB转化成了BA，也有可能是原来就是BA没有发生变化。如果是没有发生过变化，那么前一位B肯定是没有变化过的，所以我们可以得到dp[st][0]=dp[st-1][0]。如果发生过变化，就相当于之前所有的可能性，即dp[st][1]=dp[st-2][0]+dp[st-2][1]。

（这里需要注意因为是找到这两位前面的一位，所以如果这两位是刚开始，会出现dp[st][1]=0的情况，所以为了避免这种情况，还需讨论如果为0，则直接赋值为1）

③当前与前者相同（AA或者BB）

    当两个字母相同时，这个状态肯定是没有变化过的，所以dp[st][1]=0。而这个状态变化过的可能性取决于前者变化过的可能性，也就是dp[st][0]=dp[st-1][0]+dp[st-1][1]。

由上面我们归纳可得到

①当前为B，前者为A（AB）

dp[st][0]=dp[st-1][1]

dp[st][1]=0

②当前为A，前者为B（BA）

dp[st][0]=dp[st-1][0]

dp[st][1]=dp[st-2][0]+dp[st-2][1]

③当前与前者相同（AA或者BB）

dp[st][0]=dp[st-1][0]+dp[st-1][1]

dp[st][1]=0

    然后我们再去处理BA是没有变化过的情况，这里需要处理一下他的前后问题，如果BA是没变化的，而后面连接的还是BA，那么这个BA就一定是由AB转化过的。同理前面如果是BA，也一定是由AB转化过的，那么我们直接去处理在这中间有多少可能性就足够了。

    这里注意处理BABA和BABABA的情况，判断一下字符串的长度，然后决定是否还需要继续判断。

    然后我们就可以用两个函数来解决这个问题了。

    下面AC代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int dp[105][5];
char s[105];
int len;

int judge1(int st,int en)
{
    dp[st][0]=1;
    dp[en][1]=0;
    while(st!=en)
    {
        st=(st+1)%len;
        if(s[st]-1==s[(st-1+len)%len])//当前为B，前者为A
        {
            dp[st][0]=dp[(st-1+len)%len][1];
            dp[st][1]=0;
        }
        else if(s[st]+1==s[(st-1+len)%len])//当前为A，前者为B
        {
            dp[st][0]=dp[(st-1+len)%len][0];
            dp[st][1]=dp[(st-2+len)%len][0]+dp[(st-2+len)%len][1];
            if(dp[st][1]==0)
                dp[st][1]=1;
        }
        else//当前与前者相同
        {
            dp[st][0]=dp[(st-1+len)%len][0]+dp[(st-1+len)%len][1];
            dp[st][1]=0;
        }
    }
    return dp[st][0]+dp[st][1];
}

int judge2(int st,int en)
{
    int t=2;
    if(s[st]=='B')
    {
        if(s[(st+1)%len]=='A')
        {
            st=(st+2)%len;
            t+=2;
        }
        else
            return 0;
    }
    if(s[en]=='A')
    {
        if(s[(en-1+len)%len]=='B')
        {
            en=(en-2+len)%len;
            t+=2;
        }
        else
            return 0;
    }
    if(t>=len)
        return 1;
    memset(dp,0,sizeof(dp));
    dp[st][0]=1;
    dp[en][1]=0;
    while(st!=en)
    {
        st=(st+1)%len;
        if(s[st]-1==s[(st-1+len)%len])//当前为B，前者为A
        {
            dp[st][0]=dp[(st-1+len)%len][1];
            dp[st][1]=0;
        }
        else if(s[st]+1==s[(st-1+len)%len])//当前为A，前者为B
        {
            dp[st][0]=dp[(st-1+len)%len][0];
            dp[st][1]=dp[(st-2+len)%len][0]+dp[(st-2+len)%len][1];
            if(dp[st][1]==0)
                dp[st][1]=1;
        }
        else//当前与前者相同
        {
            dp[st][0]=dp[(st-1+len)%len][0]+dp[(st-1+len)%len][1];
            dp[st][1]=0;
        }
    }
    return dp[st][0]+dp[st][1];
}

int main()
{
    int i;
    int ans;
    while(scanf("%s",s)!=EOF)
    {
        memset(dp,0,sizeof(dp));
        len=strlen(s);
        for(i=0;i<len;i++)
        {
            if(s[i]-1==s[i+1])
                break;
        }
        ans=judge1((i+2)%len,(i-1+len)%len)+judge2((i+2)%len,(i-1+len)%len);
        cout<<ans<<endl;
    }
    return 0;
}