Java实现蓝桥杯算法训练 Cowboys

试题算法训练 Cowboys

问题描述

　　一个间不容发的时刻：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”。



import java.io.BufferedReader;

import java.io.IOException;

import java.io.InputStreamReader;

/**

 * 思路：动态规划、递归算法

 * ①当前为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

 */

public class Main {

    public static int dp[][] = new int[105][2];

    public static int cowboys_num;

    public static char[] cowboys_state;

    public static int state_change(int start,int end){

        dp[start][0] = 1;

        dp[start][1] = 0;

        while(start != end){

            start = (start + 1) % cowboys_num;

            //当前为B,前者为A

            if(cowboys_state[start] - 1 == cowboys_state[(start - 1 + cowboys_num) % cowboys_num]){

                dp[start][0] = dp[(start - 1 + cowboys_num) % cowboys_num][1];

                dp[start][1] = 0;

            }

            //当前为A,前者为B

            else if(cowboys_state[start] + 1 == cowboys_state[(start - 1 + cowboys_num) % cowboys_num]){

                dp[start][0] = dp[(start - 1 + cowboys_num) % cowboys_num][0];

                dp[start][1] = dp[(start - 2 + cowboys_num) % cowboys_num][0] + dp[(start - 2 + cowboys_num) % cowboys_num][1];

                if(dp[start][1] == 0){

                    dp[start][1] = 1;

                }

            }

            //当前与前者相同

            else{

                dp[start][0] = dp[(start - 1 + cowboys_num) % cowboys_num][0] + dp[(start - 1 + cowboys_num) % cowboys_num][1];

                dp[start][1] = 0;

            }

        }

        return dp[start][0] + dp[start][1];

    }

    public static int state_unchange(int start,int end){

        int t = 2;

        if(cowboys_state[start] == 'B'){

            if(cowboys_state[(start + 1) % cowboys_num] == 'A'){

                start = (start + 2) % cowboys_num;

                t += 2;

            }

            else{

                return 0;

            }

        }

        if(cowboys_state[end] == 'A'){

            if(cowboys_state[(end - 1 + cowboys_num) % cowboys_num] == 'B'){

                end = (end - 2 + cowboys_num) % cowboys_num;

                t += 2;

            }

            else{

                return 0;

            }

        }

        if(t >= cowboys_num){

            return 1;

        }

        dp = new int[105][2];

        dp[start][0] = 1;

        dp[start][1] = 0;

        while(start != end){

            start = (start + 1) % cowboys_num;

            //当前为B,前者为A

            if(cowboys_state[start] - 1 == cowboys_state[(start - 1 + cowboys_num) % cowboys_num]){

                dp[start][0] = dp[(start - 1 + cowboys_num) % cowboys_num][1];

                dp[start][1] = 0;

            }

            //当前为A,前者为B

            else if(cowboys_state[start] + 1 == cowboys_state[(start - 1 + cowboys_num) % cowboys_num]){

                dp[start][0] = dp[(start - 1 + cowboys_num) % cowboys_num][0];

                dp[start][1] = dp[(start - 2 + cowboys_num) % cowboys_num][0] + dp[(start - 2 + cowboys_num) % cowboys_num][1];

                if(dp[start][1] == 0){

                    dp[start][1] = 1;

                }

            }

            //当前与前者相同

            else{

                dp[start][0] = dp[(start - 1 + cowboys_num) % cowboys_num][0] + dp[(start - 1 + cowboys_num) % cowboys_num][1];

                dp[start][1] = 0;

            }

        }

        return dp[start][0] + dp[start][1];

    }

    public static void main(String[] args) throws IOException {

        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));

        cowboys_state = bufferedReader.readLine().toCharArray();

        int case_num = 0;

        cowboys_num = cowboys_state.length;

        int start = 0;

        for(int i = 0;i < cowboys_num;i++){

            if(cowboys_state[i] - 1 == cowboys_state[i+1]){

                start = i;

                break;

            }

        }

        case_num = state_change((start + 2) % cowboys_num,(start - 1 + cowboys_num) % cowboys_num) +

                state_unchange((start + 2) % cowboys_num,(start - 1 + cowboys_num) % cowboys_num);

        System.out.println(case_num);

    }

}

巴特西

Java实现蓝桥杯算法训练 Cowboys

试题算法训练 Cowboys

最新文章

热门文章

巴特西

Java实现 蓝桥杯 算法训练 Cowboys

试题 算法训练 Cowboys

最新文章

热门文章

Java实现蓝桥杯算法训练 Cowboys

试题算法训练 Cowboys