JG的笼子里养了n种动物,每种动物至少有1只,每种动物有互不相同数量的腿。动物种类的数量、动物总只数、动物腿的总个数是已知的。JG想要推算每种动物分别有几只,但发现答案有多种不同的解。
输入的第1行是3个正整数,分别表示动物种类的数量n、动物总只数、动物腿的总个数。输入的第2行有n个正整数,这n个正整数互不相同,分别表示第i种动物每只有几条腿(1<=i<=n)。
要求输出一共有多少种不同的解。
案例:
输入
3 4 12
2 3 4
输出
1
说明
唯一的解是2条腿的有1只,3条腿的有2只,4条腿的有1只
题目如上。
然后自己写的
#include<iostream>
using namespace std;
void anay(int legs[], int legsnum, int deep, int n, int num, int &count) {
if (deep == n - 1) {
if (num*legs[deep] == legsnum) {
count++;
}
}
else {
for (int i = 0; i <= legsnum / legs[deep]; i++) anay(legs, legsnum - i*legs[deep], deep + 1, n, num - i, count);
}
}
int main()
{
int n, num, legs, types = 0, ls = 0;
cin >> n >> num >> legs;
num -= n;//去除每种数量一只
int *ani = new int[n];
for (int i = 0; i < n; i++) {
cin >> ani[i];
ls += ani[i];
//一只的腿数
}
legs -= ls;
anay(ani, legs, 0, n, num, types);
cout << types;
return 0;
}
老师说测试数值较大会爆,请问大神们有其他思路吗