选择困难症

[编程题]选择困难症

热度指数：45 时间限制：C/C++ 3秒，其他语言6秒空间限制：C/C++ 128M，其他语言256M
算法知识视频讲解

小L有严重的选择困难症。

早上起床后，需要花很长时间决定今天穿什么出门。

假设一共有k类物品需要搭配选择，每类物品的个数为Ai，每个物品有一个喜欢值Vj，代表小L对这件物品的喜欢程度。

小L想知道，有多少种方案，使得选出来的总喜欢值>M

需要注意，每类物品，至多选择1件，可以不选。

输入描述:

多组输入
每组数据第一行输入k M(k<=6,1<=M<=1e8)，表示有多少类物品
接下来k行，每行以Ai(1<=Ai<=100)开头，表示这类物品有多少个，接下来Ai个数，第j个为Vj(1<=Vj<=1e8),表示小L对这类物品的第j个的喜欢值是多少。

输出描述:

每组输出一行，表示方案数

示例1

输入

输出

3
8

算法知识视频讲解

元气の悟空

#include<stdio.h>  
#include<string.h>  
#include<algorithm>  
using namespace std;  
int num[8],a[8][104],n,m,i,j;  
long long mul[8],res=0;
void dfs(int pos,int sum){  
    if(pos>n) return;  
    for(int i=0;i<=num[pos];i++){
        if(sum+a[pos][i]>m){  
            res+=mul[pos+1]*(num[pos]-i+1);  
            return;  
        }  
        dfs(pos+1,sum+a[pos][i]);
    }
}  
int main(){  
    while(scanf("%d%d",&n,&m)!=EOF){  
        memset(a,0,sizeof(a));  
        for(i=1;i<=n;i++){  
            scanf("%d",num+i);
            for(j=1;j<=num[i];j++) 
                scanf("%d",&a[i][j]); 
            sort(a[i]+1,a[i]+1+num[i]);
        }  
        mul[n+1]=1;
        for(i=n;i>=1;i--)
            mul[i]=mul[i+1]*(num[i]+1);  
        res=0,dfs(1,0);  
        printf("%lld\n",res);  
    }  
}

发表于 2017-11-15 00:31:01 回复(1)