一、6980: 盒子和球1
给定k个有标号的球,标号依次为1,2,…,k。
将这k个球放入m个不同的盒子里,允许有空盒,求放置方法的总数。
每个球放进盒子中均有m种方法,所以共 \(m^k\)种。
#include<bits/stdc++.h>
using namespace std;
int main()
{
int k,m;
while(cin>>k>>m)
{
long long ans=1;
//每个球均有m种放法
for(int i=0;i<k;i++)
{
ans=ans*m;
}
cout<<ans<<"\n";
}
}
二、6335: 盒子和球2
给定k个有标号的球,标号依次为1,2,…,k。
将这k个球放入m个不同的盒子里,不允许有空盒,求放置方法的总数。
问题变了麻烦起来,这直接秒杀不掉啊,需要我们考虑每一步的状态。
1.盒子不同,盒子的全排列为 \(m!\)
2.那我们尝试下k个球放进m个相同的盒子,不允许有空盒。这个问题我们需要考第i个球放进j个盒子的放法S(i,j),若单独放一盒也就是S(i-1,j-1),否则你可以选任何一个盒子放j*S(i-1,j)
递归写法,我们考虑下递归结束条件,只有1个盒子的话就1种方法
继续考虑初始值,球数 < 盒子数=0
记忆化一下,不然就超时了
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
LL ans[16][16];
LL S(LL k, LL m)
{
if(k<m)
return 0;
if(ans[k][m])return ans[k][m];
//1个盒子,全放进去
if(m==1)return 1;
//单独一盒+放进r个盒子里
return ans[k][m]=S(k-1, m-1)+m*S(k-1, m);
}
LL F(LL n)
{
if(n==0)
return 1;
return n*F(n-1);
}
int main()
{
LL k, m;
while(cin>>k>>m)
{
cout<<F(m)*S(k, m)<<endl;
}
return 0;
}
动态规划写法
只需要考虑初始状态,1个盒子放1个有1种方法,其他都来源自他,其他都是0种
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
LL dp[16][16];
LL F(LL n)
{
if(n==0)
return 1;
return n*F(n-1);
}
int main()
{
dp[1][1]=1;
for(int i=2;i<=15;i++)
{
for(int j=1;j<=i;j++)
dp[i][j]=dp[i-1][j-1]+dp[i-1][j]*j;
}
int k, m;
while(cin>>k>>m)
{
cout<<F(m)*dp[k][m]<<endl;
}
return 0;
}
三、6981: 盒子与球3
给定k个有标号的球,标号依次为1,2,…,k。
将这k个球放入m个相同的盒子里,可以有空盒,求放置方法的总数。
既然盒子数相同,那我们刚开考虑的顺序就不对了
我们可以考虑将其放进1,2,…,m个盒子
因为球不同,所以