美文网首页
北大未名湖的烦恼-解题报告

北大未名湖的烦恼-解题报告

作者: jeffleefree | 来源:发表于2016-04-18 21:50 被阅读375次

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


    tips: 此题就是dp问题,找到状态转移方程即可.

    #include<iostream>
    #include<cstdio>
    using namespace std;
    int f(int m,int n){
        if(m<n-1)
            return 0;
        if(m>0&&n==0)
            return 1;
        if(m==0&&n>1)
            return 0;
        if(m==0&&n==1)
            return 1;
        return f(m-1,n)+f(m,n-1);
    }
    int main()
    {
        int m,n;
        cin>>m>>n;
        int value = f(m-1,n);
        cout<<value;
    }
    

    相关文章

      网友评论

          本文标题:北大未名湖的烦恼-解题报告

          本文链接:https://www.haomeiwen.com/subject/rvpalttx.html