【noi 2.6_9284】盒子与小球之二（DP）

题意：有N个有差别的盒子和分别为A个和B个的红球和蓝球，盒子内可空，问方案数。

解法：我自己打的直接用了求组合C的公式，把红球和蓝球分开看。对于红球，在N个盒子可放任意个数，便相当于除了A个红球还有N个“空”球可放进N个盒子里，这些球之间是无差别的，从这N+A个球中选N个，就是C(N,N+A)。对于蓝球同理。再用乘法原理，相乘为答案。

 1 #include<cstdio>
 2 #include<cstdlib>
 3 #include<cstring>
 4 #include<iostream>
 5 using namespace std;
 6 typedef long long LL;
 7 
 8 LL C(LL x,LL y)
 9 {
10     if (x>y/2) x=y-x;
11     LL s=1;
12     for (int i=x;i>=1;i--)
13       s*=(y-i+1);
14     for (int i=x;i>=1;i--)
15       s/=i;
16     return s;
17 }
18 int main()
19 {
20     LL n,x,y;
21     scanf("%lld%lld%lld",&n,&x,&y);
22     printf("%lld
",C(n,n+x)*C(n,n+y));
23     return 0;
24 }

View Code

另外：若要用DP则是：f[i][j]表示在i个盒子中一共放j个互相无差别球的方案数。
f[i][j]=f[i-1][j]（空盒子）+f[i][j-1]（往这第i个盒子里加1个球）;再由于不需放完所有的球，方案数是f[N][0~A]和f[N][0~B]的乘积。