用php做网站需要什么软件,wordpress首页图片,营销型网站建设公司平台,广州网站商城建设机器人塔X星球的机器人表演拉拉队有两种服装#xff0c;A和B。
他们这次表演的是搭机器人塔。
类似#xff1a;队内的组塔规则是#xff1a; A 只能站在 AA 或 BB 的肩上。B 只能站在 AB 或 BA 的肩上。你的任务是帮助拉拉队计算一下#xff0c;在给定A与B的人数时…机器人塔X星球的机器人表演拉拉队有两种服装A和B。
他们这次表演的是搭机器人塔。
类似队内的组塔规则是 A 只能站在 AA 或 BB 的肩上。B 只能站在 AB 或 BA 的肩上。你的任务是帮助拉拉队计算一下在给定A与B的人数时可以组成多少种花样的塔。
输入一行两个整数 M 和 N空格分开0M,N500,分别表示A、B的人数保证人数合理性。
要求输出一个整数表示可以产生的花样种数。例如
用户输入
1 2
程序应该输出
3再例如
用户输入
3 3
程序应该输出
4资源约定
峰值内存消耗 256M
CPU消耗 1000ms
请严格按要求输出不要画蛇添足地打印类似“请您输入...” 的多余内容。
所有代码放在同一个源文件中调试通过后拷贝提交该源码。
注意不要使用package语句。不要使用jdk1.7及以上版本的特性。注意主类的名字必须是Main否则按无效代码处理。
解析由题目分析我们可以知道只要确定了最后一排的顺序就可以确定一个机器人塔我们根据这个思路只要对最后一排进行深搜将符合条件的情况记录即可。那么这样一个思路我们需要解决的首要问题就是最后一排有几个数我们要对几个“机器人”进行全排列。因为mn最多1000个人所以机器人塔最多会有50层这里稍微估计一下就能猜出。
// 求出按三角形排列从第1层到第i层有a[i]个元素非常巧妙的思路
for (int i 0; i 50; i) {sum i;a[i] sum;
}
// 求出在n个A和m个B的情况下最多能摆到第几层。
for (int i 0; i 50; i) {if (a[i] mn) {maxRow i;break;}
}
只能说有些代码巧妙地难以理解
import java.util.Scanner;public class Main {static int[] a new int[1005];static char[] s new char[1005];static int sum 0;static int m, n;static int maxRow;static int cnt 0;static int[] vis new int[1005];public static void main(String[] args) {Scanner in new Scanner(System.in);m in.nextInt();n in.nextInt();// 求出按三角形排列从第1层到第i层有a[i]个元素巧妙至极 for (int i 0; i 50; i) {sum i;a[i] sum;}// 求出在n个A和m个B的情况下最多能摆到第几层。 for (int i 0; i 50; i) {if (a[i] mn) {maxRow i;break;}}dfs(1);System.out.println(cnt);}private static void dfs(int n) {// TODO Auto-generated method stubif (n maxRow 1) {if (check(maxRow)) {cnt;}return;}if (vis[n] 0) {vis[n] 1;s[n] A;dfs(n 1);s[n] B;dfs(n 1);vis[n] 0;}}private static boolean check(int t) {char[] temp new char[1005];// 将字符串temp从第1位到第s.length()-1位给从temp的第1位开始赋值 System.arraycopy(s, 1, temp, 1, s.length-1);int sum_a 0, sum_b 0;while (t ! 0) {for (int i 1; i t; i) {if (temp[i] A) {sum_a;}if (temp[i] B) {sum_b;}}// t--代表上移一排但是采用的是对数组更新缩短 for (int i 1; i t-1; i) {if (temp[i] temp[i 1]) {temp[i] A;} else {temp[i] B;}}t--;}if (sum_a m sum_b n) {return true;}return false;}
}
