Java实现蓝桥杯算法训练 Cowboys

女爷i 2023-07-25 09:42 24阅读 0赞

## 试题 算法训练 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);
        }
    }