算法1
(暴力枚举)
本题数据范围较小,可以暴力枚举
C++ 代码
#include<bits/stdc++.h>
using namespace std;
const int N = 12;
int t,m , n;
int st[N];
//s表示目前枚举第s个人,u表示目前还有u点能量
int dfs(int s,int u){
int res = 0;
//当前枚举的人数大于n时返回,剩余能量等于0时代表方案可行,否则不可行
if(s > n ) {
if(u == 0) return 1;
else return 0;
}
//可行性剪枝,当前剩余的能量比上一个人少时返回
if(u < st[s-1]) return 0;
//每次枚举的能量都不少于上一个人,可以避免分配方案重复的问题
for (int i = st[s-1]; i <= u; i ++ ){
st[s] = i;
res += dfs(s + 1,u - i);
st[s] = 0;
}
return res;
}
int main()
{
memset(st , 0 ,sizeof st);
cin >> t;
while(t--){
cin >> m >> n;
cout << dfs(1,m) <<endl;
}
return 0;
}