C++ 解法, 执行用时: 1ms, 内存消耗: 376KB, 提交时间: 2017-09-29

#include <stdio.h>
#include <stdlib.h>
int bag[1001],n;
 
int comp(const void *a,const void *b){
    return *(int*)a - *(int*)b;
}
int dfs(int pos,long long sum,long long pi){
    int i,c;
    for(i=pos,c=0;i<n;++i){
        sum+=bag[i];
        pi*=bag[i];
        if (sum>pi) c+=1+dfs(i+1,sum,pi);
        else if (bag[i]==1) c+=dfs(i+1,sum,pi);
        else break;
        sum-=bag[i];
        pi/=bag[i];
        for(;i<n-1 && bag[i]==bag[i+1];++i);// duplicate
    }
    return c;
}
int main(){
    int i;
    while(~scanf("%d",&n)){
        for(i=0;i<n;scanf("%d",&bag[i++]));
        qsort(bag,n,sizeof(int),comp);
        printf("%d\n",dfs(0,0,1));
    }
    return 0;
}

C 解法, 执行用时: 2ms, 内存消耗: 376KB, 提交时间: 2020-08-12

#include <stdio.h>
#include <stdlib.h>

int a[1000], n;  //a存放第二行正整数各号码，n存放第一行正整数个数

int cmpfunc(const void *a, const void *b)  //快排函数
{
    return *(int*)a - *(int*)b;
}

int dfs(int cur, long long sum, long long pro)  //计算不同袋子种数的函数，需要参数：起始计算序号，起始和，起始积
{
    int c, i;  //c为要输出种类数，i为计数
    for(i = cur, c = 0; i < n; i++)  //每一次递归c都要归零，避免与前面的c重叠
    {
        sum += a[i];
        pro *= a[i];
        if(sum > pro)  //和大于积时，种类数等于‘这个的可能1个’ 加上 ‘剩下的种类数’
            c += 1 + dfs(i + 1, sum, pro);
        else if(a[i] == 1)  //否则且因为a[i]为1，导致乘法不会变大，首先这个不算，其次要算除去这一位的后面所有种类数
            c += dfs(i + 1, sum, pro);
        else break;
        sum -= a[i];  //第cur个开始的算完了，要把sum，pro归原
        pro /= a[i];
        for( ; a[i] == a[i + 1] && i < n - 1; i++);  //去重,个数增加了，但种类数没有增加
    }
    return c;  //每次循环返回的c都是从该cur起始，后面的所有号码产生的可能的“和大于积”的种数
}

int main()
{
    while(scanf("%d", &n) != EOF)
    {
        for(int i = 0; i < n; i++)
            scanf("%d", &a[i]);  
        qsort(a, n, sizeof(int), cmpfunc);  //排序的原因是方便去重
        printf("%d\n", dfs(0, 0, 1));   //dfs是一个计算符合题意的函数，返回值为幸运袋子的种数
    }
    return 0;
}