网站建设先修课程,建设网站网站首页,渭南市建设项目,公司网站建设请示报告[题目概述]
在火影忍者的世界里#xff0c;令敌人捉摸不透是非常关键的。 我们的主角漩涡鸣人所拥有的一个招数——多重影分身之术——就是一个很好的例子。 影分身是由鸣人身体的查克拉能量制造的#xff0c;使用的查克拉越多#xff0c;制造出的影分身越强。 针对不同的作…[题目概述]
在火影忍者的世界里令敌人捉摸不透是非常关键的。 我们的主角漩涡鸣人所拥有的一个招数——多重影分身之术——就是一个很好的例子。 影分身是由鸣人身体的查克拉能量制造的使用的查克拉越多制造出的影分身越强。 针对不同的作战情况鸣人可以选择制造出各种强度的影分身有的用来佯攻有的用来发起致命一击。 那么问题来了假设鸣人的查克拉能量为 M他影分身的个数最多为 N那么制造影分身时有多少种不同的分配方法 注意 影分身可以分配0点能量。 分配方案不考虑顺序例如M7,N3那么 (2,2,3) 和 (2,3,2) 被视为同一种方案。
输入格式
第一行是测试数据的数目 t。 以下每行均包含二个整数 M 和 N以空格分开。
输出格式
对输入的每组数据 M 和 N用一行输出分配的方法数。
数据范围
0 ≤ t ≤ 20, 1 ≤ M, N ≤ 10
输入样例
1
7 3输出样例
8题目就是让我们求 总和为m的能量分给n个人的方案数有多少。本题范围比较小用暴搜也能做出来但题目范围大了就不行了正确做法是DP。 状态表示f[i][j] ********集合总能量为i分给j个人的方案 ********属性count数量 状态计算 完整代码
#include iostream
#include cstring
#include cstdio
#include algorithmusing namespace std;
const int N 15;
int a[N], m, n, t;
int f[N][N];
int main (){cin t;while (t --){cin m n;memset(f, 0, sizeof f);// 初始化f[0][0] 1;for(int i 0; i m; i ){for(int j 1; j n; j ){f[i][j] f[i][j - 1];if(i j) f[i][j] f[i - j][j]; }}cout f[m][n] endl;}return 0;
}本题的分享就结束了这是整数划分问题的模板状态计算时它的划分条件很特殊别忘了点赞关注加收藏
