算法训练 未名湖边的烦恼

2018/03/26 12:51
阅读数 17


算法训练 未名湖边的烦恼  
时间限制:1.0s   内存限制:256.0MB
    
问题描述
  每年冬天,北大未名湖上都是滑冰的好地方。北大体育组准备了许多冰鞋,可是人太多了,每天下午收工后,常常一双冰鞋都不剩。
  每天早上,租鞋窗口都会排起长龙,假设有还鞋的m个,有需要租鞋的n个。现在的问题是,这些人有多少种排法,可以避免出现体育组没有冰鞋可租的尴尬场面。(两个同样需求的人(比如都是租鞋或都是还鞋)交换位置是同一种排法)
输入格式
  两个整数,表示m和n
输出格式
  一个整数,表示队伍的排法的方案数。
样例输入
3 2
样例输出
5
数据规模和约定
  m,n∈[0,18]
  问题分析


    分析:假设3个人还,2个人借,假设还为A,借为B,能够满足条件的答案为

AABB A

ABAB A

AAAB B

AABA B

ABAA B

找到的规律是,它的上一步是要么2还2借,下一次为还,要么3还1借,下一次是借

f(int m, int n)

{

     .......

     return f(m - 1, n) + f(m, n - 1); // 分别为下一次为还,下一次为借

}

如果依次递归到借的n == 0,那么不借肯定成立,这是一种情况,题目说明两个同样需求的人(比如都是租鞋或都是还鞋)交换位置是同一种排法,那么3个A,还的顺序不同也算一种情况。

至于f(m - 1, n) + f(m, n - 1)的前一种情况f(m-1, n),可能出现之后m < n,那么不成立,return 0,接着到f(m, n-1)情况去,会递归到n == 0情况,这样所有可能的情况都包含了

有人会想m == n情况,或者m>=n情况,这些不用判断,m==n,可能BAAB,BBAA,BABA,ABBA这些都不成立的,只需要跟着最初列出的递归式子想就行了,最后加上动态规划,速度就有所提升。

import java.io.BufferedInputStream;
import java.util.Scanner;

public class Main {
    public static int[][] dp = new int[19][19];

    public static int f(int m, int n) {
        if (dp[m][n] != -1)
            return dp[m][n];
        if (m < n)
            return dp[m][n] = 0;
        if (n == 0)
            return dp[m][n] = 1;
        return dp[m][n] = f(m, n - 1) + f(m - 1, n);// 分别为此次借,此次还,情况相加即为所求
    }

    public static void main(String[] args) {
        Scanner cin = new Scanner(new BufferedInputStream(System.in));
        int m = cin.nextInt();
        int n = cin.nextInt();
        cin.close();
        for (int i = 0; i < 19; ++i) {
            for (int j = 0; j < 19; ++j) {
                dp[i][j] = -1;
            }
        }
        System.out.println(f(m, n));
    }
}


========================================Talk is cheap, show me the code=======================================

展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部