住房和城乡建设网站,注册服务公司流程和费用,百度做网站怎么样,天津网站建设 seo题干#xff1a;
把M个同样的苹果放在N个同样的盘子里#xff0c;允许有的盘子空着不放#xff0c;问共有多少种不同的分法#xff1f;#xff08;用K表示#xff09;5#xff0c;1#xff0c;1和1#xff0c;5#xff0c;1 是同一种分法。
Input
第一行是测试数据…题干
把M个同样的苹果放在N个同样的盘子里允许有的盘子空着不放问共有多少种不同的分法用K表示511和151 是同一种分法。
Input
第一行是测试数据的数目t0 t 20。以下每行均包含二个整数M和N以空格分开。1MN10。
Output
对输入的每组数据M和N用一行输出相应的K。
Sample Input
1
7 3Sample Output
8
解题报告
dp解法
// 定义dp[i][j]为把i个苹果放在j个盘子里的放法 // dp[i][j] dp[i][j-1] 或者 // dp[i][j] dp[i][j-1] dp[i-j][j] // // 如果j个盘子中有空盘子那么就转换成dp[i][j-1] // 如果没有空盘子我们就先给这j个盘子放每个盘子放一个苹果 // 转换成dp[i-j][j]
AC代码1dp解法
#include cstdio
#include iostream
#include cstring
using namespace std;const int MAX 15;
int dp[MAX][MAX];
int M,N;
int main() {int T;cinT;while(cinMN) {memset(dp,-1,sizeof(dp));for(int i 1; i10; i) dp[0][i] dp[1][i] dp[i][1] 1;for(int i 1; i 12; i) {for (int j 1; j12; j) {if (ij) //证明有空盘子dp[i][j] dp[i][j-1];else //证明没有空盘子那就先给这j个盘子里面每个//都放一个苹果转换成dp[i-j][j];dp[i][j] dp[i][j-1] dp[i-j][j];}}coutdp[M][N]endl;}
}
AC代码2
//母函数模板题M个相同球放到N个相同的盒子中 G(x) (1xx^2x^3...x^k...)*(1xx^2x^3...x^k...)*...一共有 n 项我们要求的就是x^m前面的系数
#includeiostream
#includecstdio
#includecstring
#includealgorithm
#includeset
#includecmath
using namespace std;
int n;
struct Z{
int val;
int num;
}z[10000];
int ans[100005],ans0[100005];
int main(){
int t;
cint;
while(t--){int m,n;cinmn;for(int i0;im;i){ans[i]1;ans0[i]0;}for(int i2;in;i){for(int j0;jm;j){for(int k0;jkm;ki)ans0[jk]ans[j];}for(int j0;jm;j){ans[j]ans0[j];ans0[j]0;}}coutans[m]endl;
}
}
有个看不懂的题解关于母函数https://www.luogu.org/problemnew/solution/P1025。。。神仙构造的感觉
