问题描述
每年冬天, 北大未名湖上都是滑冰的好地方北大体育组准备了许多冰鞋, 可是人太多了, 每天下午收工后, 常常一双冰鞋都不剩
每天早上, 租鞋窗口都会排起长龙, 假设有还鞋的 m 个, 有需要租鞋的 n 个现在的问题是, 这些人有多少种排法, 可以避免出现体育组没有冰鞋可租的尴尬场面 (两个同样需求的人(比如都是租鞋或都是还鞋) 交换位置是同一种排法)
输入格式
两个整数, 表示 m 和 n
输出格式
一个整数, 表示队伍的排法的方案数
样例输入
3 2
样例输出
5
数据规模和约定
m,n[0,18]
问题分析
题解
- #include<stdio.h>
- #include<algorithm>
- #include<string.h>
- using namespace std;
- int main()
- {
- int n, m; //m 表示换鞋, n 表示借鞋
- int f[20][20]; //f[x][y] 表示取借鞋和换鞋的数目 x,y
- memset(f, 0, sizeof(f));
- scanf("%d %d", &n, &m);
- for(int i = 1; i <= n; i++)
- f[i][0] = 1;
- for(int i = 1; i <= m; i++)
- f[0][i] = 1;
- for(int i = 1; i <= n; i++)
- {
- for(int j = 1; j <= m; j++)
- {
- if( i == j)
- f[i][j] = f[i][j-1];
- else if(i > j)
- f[i][j] = f[i-1][j] + f[i][j-1];
- }
- }
- printf("%d\n", f[n][m]);
- return 0;
- }
- View Code
算法训练 未名湖边的烦恼 (递推)
来源: http://www.bubuko.com/infodetail-2488770.html