蓝桥杯练习题C

题目来源:http://oj.mofriend.net/problem.php?cid=1203&pid=2

题目描述
把M个同样的苹果放在N个同样的盘子里,允许有的盘子空着不放,问共有多少种不同的分法?(用K表示)5,1,1和1,5,1 是同一种分法

输入
输入数据只有一行包含二个整数M和N,以空格分开。1<=M,N<=100
输出
输出相应的分法。(结尾加一个换行符)

1
2
3
4
样例输入
4 2
样例输出
3

思路:
这题看起来很简单,但是实现起来会 超时,需要配合动态规划来实现.
首先他要求区分 5,1,1和1,5,1 所以我的第一个应对思路 是 第一个盘子如果放1 个 第二个盘子的数量 要大于等于第一个盘子的数量 第三个盘子的数量要 大于等于第二个盘子的数量 这样的结果是不会重复计算的
举个例子 5 3
1 1 3
1 2 2
1 4 0
2 3 0
5 0 0
一共这5个
代码写完后发现超时 ,当N,M> 80的时候 跑 5 – 6秒都跑不出结果
所以就得加上动态规划
动态规划 数组 a[100][100][100];
a[i][j][k] i j k 的意思分别是 盘子起始最少放苹果数量, 剩余盘子数量, 当前苹果数.
当第一个盘子 放入 1 个的时候 程序会查 a[1][3-1][5-1] 这个表来查看 当i j k 为 1 2 4的时候程序之前是否计算过,若计算过就可以直接从表出读出来,不用接着往下搜索,
这样的动态规划适用于 递归,并且问题会重复发生的时候来使用.
代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <iostream>
using namespace std;
int m; int n;
int a[101][101][101];
int select(int i, int k, int sum) {
if (k>n || sum>m)return 0;
if (sum == m) {
return 1;
}
int qq = 0;
if (a[i][m - k][n - sum] != 0)return a[i][m - k][n - sum];
for (int j = i; j <= m; j++)
{
if (sum + i <= m)
qq = qq + select(j, k + 1, sum + j);
}
a[i][m - k][n - sum] = qq;
return qq;
}
int selectmain(int i, int k) {
int sum = 0;
for (int j = 1; j <= m; j++)
{
sum = sum + select(j, k + 1, j);
}
return sum;

}
int main(int argc, char** argv) {
memset(a, 0, sizeof(int) * 100 * 100 * 100);
cin >> m >> n;
int sum = selectmain(0, 0);
cout << sum << endl;
return 0;
}