stonechina0616

描述

N个有差别的盒子（1<=N<=20）。你有A个红球和B个蓝球。0 <= A <= 15, 0 <= B <= 15。球除了颜色没有任何区别。你可以将球放进盒子。一个盒子可以同时放进两种球，也可以只放一种，也可以空着。球不必全部放入盒子中。编程计算有多少种放置球的方法。 

输入

就一行，N，A，B，用空格分开

输出

就一行，输出放置方案总数

样例输入2 1 1样例输出9

典型的动态规划，无需用到组合数的知识

dp[k][i][j]表示前k个盒子放入i个红球和j个蓝球，得到以下转移：

dp[k][i][j]=dp[k-1][i][j]+dp[k][i-1][j]+dp[k][i][j-1]-dp[k][i-1][j-1]

dp[k-1][i][j]表示从k-1个盒子中放入i个红球和j个蓝球，即第k个盒子不放球

dp[k][i][j-1]表示在第k个盒子中再放入一个蓝球

dp[k][i-1][j]表示从第k个盒子中再放入一个红球

转移时将方案累加，但是可以发现，其中有一个状态是重复的，即在一个盒子中放入一个蓝球和一个红球，所以减去这一方案数。

代码：

#include<cstdio>

#include<iostream>

#include<algorithm>

#include<cstring>

#include<cmath>

#define rep(q,p) for (int q=1;q<=p;q++)

#define db double

using namespace std;

const int maxn=25;

int n,a,b;

long long dp[maxn][maxn][maxn];

int main()

{

    freopen("in.txt","r",stdin);

    scanf("%d%d%d",&n,&a,&b);

    for (int i=0;i<=a;i++)

        for (int j=0;j<=b;j++)

            dp[0][i][j]=1;

    rep(k,n)

        for (int i=0;i<=a;i++)

            for (int j=0;j<=b;j++)

                dp[k][i][j]=dp[k-1][i][j]+dp[k][i-1][j]+dp[k][i][j-1]-dp[k][i-1][j-1];

    printf("%lld\n",dp[n][a][b]);

    ​return 0;

}