本文共 1420 字，大约阅读时间需要 4 分钟。

选择困难症

链接：https://ac.nowcoder.com/acm/problem/13594

来源：牛客网

题目描述

小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 输入 2 5 3 1 3 4 2 2 3 2 1 2 2 2 2 2 2 输出 3 8

先贴源码：

#include
   
    using namespace std;typedef long long ll;const int maxn = 105;int a[7][maxn];//存储数据ll k,m,sum;int b[7];void dfs(int lev,int val){           if(val>m)    {           ll res = 1;        for(int i=lev;i<=k;i++)        {               res *= (b[i]+1);        }        sum += res;        return ;    }    if(lev>k) return;//层数超出限制    for(int i=0;i<=b[lev];i++)    {           dfs(lev+1,val+a[lev][i]);    }}int main(){       while(cin>>k>>m)    {           sum = 0;        for(int i=1;i<=k;i++)        {               cin>>b[i];            for(int j=1;j<=b[i];j++)            {                   cin>>a[i][j];            }        }        dfs(1,0);        cout<
    
     <<"\n";    }    return 0;}
    
   

手写图解：

思路解析：

对于每类的数据，可以把它理解为树的每一层。

每层的树都要面临 b[i]+1 种选择，把它理解为每个节点的子节点。

因为每层（每类的物品）都要进行选择，要么选一个，要么不选，每类物品都是如此，所以就要dfs进行搜索，递归进行下去。

我对递归的一点理解：就是每次数据进行处理的步骤都是类似的，比如本题，每类的物品都要进行选择，就可以用递归来做。

本题对于dfs的终点的解读：

必须先判断累加的值是否大于给定的m，因为如果先判断是否出界，最后一类物品可能满足取的价值和已经大于m，但是因为先判断出界而没有算上最后一类物品导致少算。

感兴趣可关注公众号领取大量资料。

转载地址：http://znrq.baihongyu.com/