选择困难症

题目链接：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个的喜欢值是多少。

输出描述

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

示例

输入

2 5
3 1 3 4
2 2 3
2 1
2 2 2
2 2 2

输出

3
8

分析

本题是非常经典的入门型深搜题目，重点是掌握这种写法，观察这个dfs函数。
这个题需要注意一下优化，一旦某一层已经出现喜好度之和大于m，就不必再搜下去了，处理见代码。
另外 注意数据范围 必须上long long。

AC代码

---

#include <string>
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;

int k, m;
int v[6][102];
long long ans;

void dfs(int n, int val)    //n为层数 val为当前的喜好度和
{
    if (val > m)    //这个判断应该放在层数判断之前
    {
        long long sum = 1;
        for (int i = n; i < k; i++)
        {
            sum *= (v[i][0] + 1);   //别忘了加0这种情况
        }
        ans += sum;
        return;
    }
    if (n == k)
        return;
    for (int i = 1; i <= v[n][0] + 1; i++)
        dfs(n + 1, val + v[n][i]);
}

int main()
{
    while (cin >> k >> m)
    {
        for (int i = 0; i < k; i++)
        {
            cin >> v[i][0];
            v[i][v[i][0] + 1] = 0;  //这里把0的情况放在最后了
            for (int j = 1; j <= v[i][0]; j++)
            {
                cin >> v[i][j];
            }
        }
        ans = 0;
        dfs(0, 0);
        cout << ans << endl;
    }
    return 0;
}