1011.盒子与球

Time Limit: 1000 MS Memory Limit: 32768 KB
Total Submission(s): 688 Accepted Submission(s): 170

Description

现有r个互不相同的盒子和n个互不相同的球，要将这n个球放入r个盒子中，且不允许有空盒子。则有多少种放法？

Input

n, r(0 <= n, r <= 10)。

Output

有多少种放法。

Sample Input

3 2

Sample Output

6

这道题刚开始一直想用排列组合来做，结果发现更不会了。。。需要思考的东西太多，之后发现了这个第二类string函数来解决这道题。
大意是这样的，首先先认为这10个盒子是一样的，于是在有b个盒子a个球的情况下n[a][b],是可以由之前的n[a-1][b-1]和n[a-1][b]决定的
n[a][b]=n[a-1][b-1]+n[a-1][b]*b;
地推来做，初始条件为n[1][1]=1;
其余情况先定位0；
最后答案在乘之前隐藏的盒子互不相等的条件。

#include<cstdio>
#include<iostream>
using namespace std;
int main()
{
    int m[11] = { 1,1,2,6,24,120,720,5040,40320,362880,3628800 };
    int n[11][11] = { 0 };
    n[1][1] = 1;
    int a, b;
    cin >> a >> b;
    for (int c = 2; c <= a; c++)
    {
        for (int d = 1; d <= b; d++)
        {
            n[c][d] = n[c - 1][d - 1] + n[c-1][d] * d;
        }
    }
    printf("%d\n", n[a][b] * m[b]);
    return 0;
}