题解 P1287 【盒子与球】

was_n · 2017-09-12 14:06:11 · 题解

这道题是一个比较弱的dp，转移方程f[i][j]=f[i-1][j-1]+j*[i-1][j]

其实比较好想，如果前面的盒子被填满了，那么最后一个球有j种方法；

如果没填满则=f[i-1][j-1]

#include<cstdio>
#include<iostream>
using namespace std;
int n,r,f[100][100]={1};
int jc(int k)
{
    int ans=1;
    for(int i=2;i<=k;i++)
    {
        ans*=i;
    }
    return ans;
}
int main()
{
    cin>>n>>r;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=r;j++)
        {
            f[i][j]=f[i-1][j-1]+j*f[i-1][j];
        }
    }
    cout<<f[n][r]*jc(r);
    return 0;
}