stonechina0616

给定N个各不相同的小球，和M个不同的BOX，有多少种不同的放球方法，使得每个BOX里的小球个数不小于Ｋ。N,M,K均小于15

每行给出Ｎ,M,K 

以0 0 0结束

如题

正如之前的盒子与小球之二、之三，这种求组合方案的通用方法就是DP

dp[i][j]表示前i个装入j个小球的方案数，转移时和盒子与小球系列的其他题很相似，都是枚举第i个盒子放入小球的数量，但这里应该注意小球是不同的，所以要预处理出组合数。

DP方程：

dp[i][j]=Σdp[i-1][j-p]*C[n-(j-p)][p]    (p>=k)

具体含义：

第i个盒子中放入p个小球(p>=k)，这些小球是不同的，所以乘上组合数，然后累加

代码：

#include<cstdio> #include<iostream> #include<algorithm> #include<cstring> #define rep(q,p) for (int q=1;q<=p;q++) #define db double using namespace std; const int maxn=20; int n,m,k; long long dp[maxn][maxn],c[maxn][maxn]; int main() { for (int i=0;i<=15;i++) c[i][0]=1; rep(i,15) rep(j,15) c[i][j]=c[i-1][j]+c[i-1][j-1]; while (scanf("%d%d%d",&n,&m,&k),n!=0 || m!=0 || k!=0) { memset(dp,0,sizeof(dp)); for (int i=k;i<=n;i++) dp[1][i]=c[n][i]; for (int i=2;i<=m;i++) for (int j=k;j<=n;j++) for (int p=k;p<=j;p++) dp[i][j]+=dp[i-1][j-p]*c[n-(j-p)][p]; printf("%lld\n",dp[m][n]); } return 0; }