ZSTUOJ 三只小猪

朴灿烈づ我的快乐病毒、 2023-06-27 05:46 21阅读 0赞

## Problem : 三只小猪 ##

### Description ###

这日，快码佳编四兄弟姐妹来到了一个山脚下，只听一个老奶奶给两个孙子讲故事。  
你听说过三只小猪的故事吗？这是一个经典的故事。很久很久以前，有三只小猪。第一只小猪用稻草建的房子，第二个小猪用木棍建的房子，第三个小猪则使用砖做为材料。一只大灰狼想吃掉它们并吹倒了稻草和木棍建的房子。但是砖盖的房子很结实，狼最终也没有破坏掉，最后小猪们战胜了大灰狼并把它尾巴烧掉了。  
为了自己的安全，小猪们又建造了一个新砖房。但是现在问题出现了，怎样把三个小猪分配到两个房子里呢？第三只小猪是三只小猪中最聪明的一只，为了不浪费任何一个房子，它总共考虑了三种方案，如下图  
![Alt][]

但是将来怎么办呢？”第三只小猪知道将来随着成员的增多，它们将会盖更多的房子。它想知道给定了房子和猪的数目后，房子的分配方案有多少，但这个问题对于它来说，很明显有点难了，你能帮小猪解决这个问题吗？

### Input ###

多组测试，每组 仅有一行，包含两个整数n和m，分别表示小猪的数目和房间数（1≤n≤20，0≤m≤20）

### Output ###

每组输出一行，仅一个整数，表示将n只小猪安置在m个房间且没有房间空闲的方案数。

### Sample Input ###

4 2

### Sample Output ###

### 思路： ###

n只小猪放到m房子，不允许有空房子，  
这里，我们用 dp\[m\]\[n\] 来表示情况总数  
首先我们可以直接想出这么几种情况：  
1.如果过m>n,肯定有空房子，那么 就是0种情况。

2.如果m=n，那么每一只小猪肯定都要分配到不同房子 就是1种情况。

3.如果m=1，而且n>0，那么，所有小猪都在一个房子，也是1种情况 展示代码如下：

for(int i=1;i<=n;i++)//一个房间小猪分配的情况 
    			dp[1][i]=1;

现在，特殊的情况知道了，那么，我们想一般的情况；

我们按照提示的图来分析下： n=3，m=2；情况数目为dp\[2\]\[3\]  
三只小猪 x1，x2，x3；  
有这么三种情况：  
**x1 x2 | x3  
x1 x3 | x2  
x2 x3 | x1**  
此时**dp\[3\]\[2\]=3**  
那么 如果 再来一只小猪x4呢（在房子数目不变情况下）  
首先 针对**x1 x2 | x3** 这种情况 x4 可以插入到2个房子（m个房子）中去  
然后和**x1 x2 | x3** 并列的情况有三种  
那么此时**dp\[2\]\[4\]=2\*dp\[2\]\[3\]**  
即**dp\[2\]\[4\]=2\*dp\[2\]\[4-1\]**

但是除此之外，x4也可能单独一个房间，此时的情况是原先三只小猪分配到1个房子 **dp\[1\]\[3\]**  
即**dp\[2-1\]\[4-1\]**

归纳总结可以得出状态转移方程

dp[m][n] = dp[m][n-1]*m + dp[m-1][n-1]

### 代码 ###

#include<bits/stdc++.h>
    using namespace std;
    int main()
    {
        
    	long long dp[25][25];
    	int m,n;
    	while(cin>>n>>m)
    	{
        
    		memset(dp,0,sizeof(dp));
    		for(int i=1;i<=n;i++)//一个房间小猪分配； 
    			dp[1][i]=1;
    		for(int i=2;i<=m;i++)//m个房间 
    			for(int j=1;j<=n;j++)//n只小猪分配 
    				dp[i][j]=dp[i][j-1]*i+dp[i-1][j-1]; 
    		cout<<dp[m][n]<<endl;
    	}
    	return 0;
    }

[Alt]: https://imgconvert.csdnimg.cn/aHR0cDovL29qLmFjbS56c3R1LmVkdS5jbi9KdWRnZU9ubGluZS91cGxvYWQvMjAxOTAxL3podS5wbmc?x-oss-process=image/format,png