題目描述
一個袋子里面有n個球缰雇，每個球上面都有一個號碼(擁有相同號碼的球是無區(qū)別的)混移。如果一個袋子是幸運的當且僅當所有球的號碼的和大于所有球的號碼的積。
例如：如果袋子里面的球的號碼是{1, 1, 2, 3}，這個袋子就是幸運的档插，因為1 + 1 + 2 + 3 > 1 * 1 * 2 * 3
你可以適當從袋子里移除一些球(可以移除0個,但是別移除完)，要使移除后的袋子是幸運的⊙窃伲現(xiàn)在讓你編程計算一下你可以獲得的多少種不同的幸運的袋子郭膛。
輸入描述:
第一行輸入一個正整數(shù)n(n ≤ 1000)
第二行為n個數(shù)正整數(shù)xi(xi ≤ 1000)
輸出描述:
輸出可以產(chǎn)生的幸運的袋子數(shù)
示例1
輸入
3
1 1 1
輸出
2
題解：
/*
思路：
1.如果a+b>a*b,則必有一個數(shù)為1。
2.證明：設a=x+1,b=y+1,(x+1)+(y+1)>(x+1)(y+1) => 1>x*y => 由于題中a,b為正整數(shù),x,y必有一個為0 =>x,y必有一個為1氛悬；
3.推廣到a1,a2,a3...ak. 如果sum<=pi:
sum+am>pi*ak+m => am必為1则剃，但am為1，不一定能得到前者
如果am>1,則sum+am<=pi*am一定成立如捅。（得到剪枝的重要依據(jù)）
*/
#include<cstdio>
#include<set>
#include<algorithm>
using namespace std;
int n;
int num[1010];
bool cmp(int a, int b) {
return a < b;
}
int dfs(int index, long long sum, long long mult) {
int cnt = 0;
for (int i = index; i < n; i++) {
sum += num[i];
mult *= num[i];
if (sum > mult) {
cnt += 1 + dfs(i + 1, sum, mult);
}
else if (num[i] == 1) {
cnt += dfs(i + 1, sum, mult);
}
else break;
sum -= num[i];
mult /= num[i];
for (; i < n - 1 && num[i + 1] == num[i]; i++);
}
return cnt;
}
int main() {
scanf("%d", &n);
for (int i = 0; i<n; i++) {
scanf("%d", &num[i], cmp);
}
sort(num, num + n);
printf("%d", dfs(0,0,1));
return 0;
}
