算法训练 Cowboys（DP）

问题描述

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

输入格式

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

输出格式

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

数据规模和约定

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

样例输入

BABBBABBA

样例输出

样例输入

ABABB

样例输出

样例输入

ABABAB

样例输出

样例说明

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

题解

#include<bits/stdc++.h>

using namespace std;

long long  dp[][]={};

int main(){

    dp[][]=;

    dp[][]=;

    dp[][]=;

    dp[][]=;

    for(int i=;i<=;i++){         //打表dp情况数

        dp[i][]=dp[i-][];

        dp[i][]=dp[i-][];

        dp[i][]=dp[i-][]+dp[i-][];

        dp[i][]=dp[i-][];

    }

    string target;

    int length,i;

    while(cin>>target){

        length=target.size();

        string tmp1="",tmp2="";     //检查是否存在全A或者全B情况

        for(int k=;i<length;k++){

            tmp1+="A";

            tmp2+="B";

        }

        if(target==tmp1||target==tmp2){

            cout<<<<endl;

            return ;

        }

        if(length%==){

            tmp1="";

            tmp2="";

            for(int i=;i<=length/;i++){   //检查是否全串都是一个BA串！

                tmp1+="AB";

                tmp2+="BA";

            }

            if(tmp1==target||tmp2==target){

                cout<<dp[length/-][]+dp[length/-][]<<endl;

                return ;

            }

        }

        for(i=;i<length;i++){              //找到第一组BA开始位置

            if(target[i]=='B'&&target[(i+)%length]=='A'){

                break;

            }

        }

        for(int j=i;;j=(j+)%length){       //找到第一组BA结束位置

            if(target[j]!='B'||target[(j+)%length]!='A'){

                i=j;

                break;

            }

        }

        int times=,start,end;

        long long ans=;

        for(int j=i;j<i+length;j++){

            if(target[j%length]=='B'&&target[(j+)%length]=='A'){

                if(times==){

                    start=(j+length-)%length;      //记录开始位置，记得-1

                }

                times++;

                j++;            //循环中有++那么这里再++就够了

            }

            else {

                if(times!=){           //如果已经记录了BA组数

                    end=j%length;       //记录结束位置

                    if(target[start]=='A'&&target[end]=='A')        ans*=dp[times][];

                    else if(target[start]=='A'&&target[end]=='B')   ans*=dp[times][];

                    else if(target[start]=='B'&&target[end]=='A')   ans*=dp[times][];

                    else if(target[start]=='B'&&target[end]=='B')   ans*=dp[times][];

                    times=;            //一个串记录的组数清零

                }

            }

        }

        if(times!=){                   //别忘了最后一组！看我实现构造的方法，最后一组是被忽略掉的

            end=i%length;

            if(target[start]=='A'&&target[end]=='A')        ans*=dp[times][];

            else if(target[start]=='A'&&target[end]=='B')   ans*=dp[times][];

            else if(target[start]=='B'&&target[end]=='A')   ans*=dp[times][];

            else if(target[start]=='B'&&target[end]=='B')   ans*=dp[times][];

        }

        cout<<ans<<endl;

    }

    return ;

}

没看懂系列（（（（（

巴特西

算法训练 Cowboys（DP）

最新文章

热门文章