题解 P1287 【盒子与球】

listenteresaX · 2018-07-18 16:02:18 · 题解

一道动规题，没用stirling数（斯特林数） 那写的什么鬼

#include<iostream>
#include<cstdio>
using namespace std;
int n,m;
long long f[15][15];
int main()
{
    cin>>n>>m;
    if(n==0||m>n)//球少于盒子则无解，至于0个球，姑且算0种方案吧 
    {
        cout<<0<<endl;
        return 0;
    }
    f[1][1]=1;//明显边界 
    for(int i=2;i<=n;i++)
    for(int j=1;j<=min(i,m);j++)
    f[i][j]=j*(f[i-1][j]+f[i-1][j-1]);//最后一球放入单独一盒子，共j*f[i-1][j-1];
                                      //共用盒子，则有j*f[i-1][j]种 
    cout<<f[n][m]<<endl;
    return 0;
}