盒子和小球之二：N个有差别的盒子（1<=N<=20）。你有A个红球和B个蓝球。0 <= A <= 15, 0 <= B <= 15。球除了颜色没有任何区别。你可以将球放进盒子。一个盒子可以同时放进两种球，也可以只放一种，也可以空着。球不必全部放入盒子中。编程计算有多少种放置球的方法。
考虑动态规划。一个盒子可以同时放进两种球，但是每个盒子我们可以对他进行很多操作，所以也就可以近似看成每个盒子可以放无数球，但是这并不重要。设f[i][j][k]表示我们当前放到第i个盒子，已经放了j个红球，k个篮球的状态方案数。（因为我们要求在状态设计的时候要求顾及到题目中的重要量，而这个状态恰好达到了这点）另外，由于本题数据范围较小，所以我们思考的不用太复杂。
则我们可以理所当然地想到转移：f[i][j][k]=sigmaf[i-1][j-x][k-x],其中x是我们枚举的在当前盒子中放几个。
时间复杂度为O（n*A^2*B^2)，可以轻松通过。
目标答案显然我们可以累加f[n][i][j]，枚举ij。
#include<cstdio>
#include<algorithm> using namespace std;
typedef long long ll;
//complexity n*A^2*B^2
int n,A,B;
ll ans,f[][][]; int main()
{
scanf("%d%d%d",&n,&A,&B);
f[][][]=;//初值，很重要
for(int i=;i<=n;i++)
for(int j=;j<=A;j++)//注意放几个从0开始枚举
for(int k=;k<=B;k++)
for(int a=;a<=j;a++)
for(int b=;b<=k;b++)
f[i][j][k]+=f[i-][j-a][k-b];
for(int i=;i<=A;i++)
for(int j=;j<=B;j++)
ans+=f[n][i][j];//球不必全部放入盒子中
printf("%lld",ans);
return ;
}
盒子与小球之三：有N个相同的球，M个不同的盒子，每个盒子最多放K个球 ，请计算将这N个球全部放入盒子中的方案数模1000007后的结果 ，N<=5000，M<=5000。
我们可以继续考虑动态规划，相似的状态与转移。设f[i][j]为当前放到第i个盒子，已经放了j个球的方案数。显然有转移：
f[i][j]=sigmaf[i-1][j-k]，其中k枚举在当前盒子里放了几个。但由于本题数据比上一题大很多，这样的n^3转移会超时。状态设计的没有什么可以优化的了，考虑在转移优化。我们仔细观察转移方程，发现我们要加的其实是连续的一段，这就启示我们可以用前缀和优化，在转移前提前算出在i-1状态下的j前缀和。
#include<cstdio>
#include<algorithm>
#define maxn 5090 using namespace std;
typedef long long ll; int n,m,k;
ll moder=,f[maxn][maxn],sum[maxn]; int main()
{
scanf("%d%d%d",&n,&m,&k);
for(int i=;i<=m;i++) f[i][]=;
for(int i=;i<=m;i++)
{
for(int j=;j<=n;j++)
(sum[j]=sum[j-]+f[i-][j])%=moder;
for(int j=;j<=n;j++)
{
//if(i==1&&j==1) printf("~~~~%d %d %d\n",sum[j],sum[max(j-k-1,0)],max(j-k-1,0));
if(j-k-<) (f[i][j]=sum[j]+moder)%=moder;
else (f[i][j]=sum[j]-sum[j-k-]+moder)%=moder;
//printf("%d %d:=%d\n",i,j,f[i][j]);
}
}
printf("%lld",f[m][n]);
return ;
}
盒子与小球之四：给定N个各不相同的小球，和M个不同的BOX，有多少种不同的放球方法，使得每个BOX里的小球个数不小于Ｋ。N,M,K均小于15。
我们还可以继续考虑动态规划。设f[i][j]表示当前放到第i个盒子，已经放了j个球的方案数。小球个数不小于k，只需要在转移时从k开始枚举。由于本题小球各不相同，所以我们需要组合数。本题数据在15，非常小可以递推预处理出组合数。于是有转移如下：
f[i][j]=sigmaf[i-1][j-k]*C(n-(j-k),k).
#include<cstdio>
#include<algorithm>
#include<cstring> using namespace std;
typedef long long ll; int n,m,jue;
ll f[][],C[][]; ll Combines()
{
for(int i=;i<=;i++) C[i][]=,C[i][i]=;
for(int i=;i<=;i++)
for(int j=;j<=i;j++)
C[i][j]=C[i-][j]+C[i-][j-];
} int main()
{
Combines();
while(scanf("%d%d%d",&n,&m,&jue)!=EOF&&n!=)
{
memset(f,,sizeof f);
for(int i=jue;i<=n;i++) f[][i]=C[n][i];
for(int i=;i<=m;i++)
for(int j=jue;j<=n;j++)
for(int k=jue;k<=j;k++)
f[i][j]+=C[n-(j-k)][k]*f[i-][j-k];
printf("%lld\n",f[m][n]);
}
return ;
}