蓝桥杯决赛javaA组---机器人塔

题目描述

X星球的机器人表演拉拉队有两种服装，A和B。
他们这次表演的是搭机器人塔。

类似：
A
B B
A B A
A A B B
B B B A B
A B A B B A

队内的组塔规则是：

A 只能站在 AA 或 BB 的肩上。
B 只能站在 AB 或 BA 的肩上。
你的任务是帮助拉拉队计算一下，在给定A与B的人数时，可以组成多少种花样的塔。
输入一行两个整数 M 和 N，分别表示A、B的人数，保证人数合理性。
要求输出一个整数，表示可以产生的花样种数。

例如：
用户输入：
1 2

程序应该输出：
3

再例如：
用户输入：
3 3

程序应该输出：
4

资源约定：
峰值内存消耗 < 256M
CPU消耗 < 1000ms

解题思想

/* 对于这种类型的题，一般有俩种思考方法 1.从上向下构造解 2.从下向上构造解 对于本题，显然是从下向上比较好。为什么这么说呢？ 从下向上，已知下面一层的2个数，可以唯一确定上面一层的那个数 然而，如果从上向下，大家自己想一下，是不是感觉情况很多。 所以，总体的解题思路： 首先利用《《不重复排列列 DFS解法》》，来对最后一层进行不重复的全排列，然后依次往上一层进行构造，如果全部构造完成，则满足条件 */

《不重复排列列 DFS解法》请先看
http://blog.csdn.net/dragonlogin/article/details/72667207

代码

import java.util.Scanner;
public class Main{
    static int[][] tem = null;
    static int[] vis = null;
    static int[] arr = {1,2};
    static int  death ;
    static int a, b , ant=0;
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        a = sc.nextInt();
        b = sc.nextInt();
        //init
        death = (int)Math.sqrt((a+b)*2);
        tem = new int[death][death];
        vis = new int[2];
        vis[0] = a;
        vis[1] = b;
        dfs(0);
        System.out.println(ant);

    }
    static void dfs(int step){
        if(step == death){
            if(check())
                ant++;
            return;
        }

        for(int i=0; i<=1; ++i){
            if(vis[i] > 0){
                vis[i]--;
                tem[death-1][step] = arr[i];
                dfs(step+1);
                vis[i]++;
            }
        }
    }
    public static boolean check(){
        int m = a; //A的数量
        int n = b; //B的数量
        //最后一层，分别用走的A,B的数量
        for(int i=0; i<death; ++i)
            if(tem[death-1][i] == 1)
                m--;
            else
                n--;
                //依次向上构造每一层
        for(int i=death-2; i>-1; --i){ 
        //减2的原因，death就是最后一层的数目，
        //减1表示下标从0开始
        //再减一表示从倒数第二层开始构造
            for(int j=0; j<=i; ++j){
                if(tem[i+1][j] != tem[i+1][j+1]){
                //若下一层不相等，本层就放B
                    tem[i][j] = 2;
                    n--;
                    if(n<0)
                        return false;
                }else{
                //否则相等，放A
                        tem[i][j] = 1;
                        m--;
                        if(m<0)
                            return false;
                    }
                }
            }
        return true;
    }
}