选择困难症

题目描述 小L有严重的选择困难症。 早上起床后，需要花很长时间决定今天穿什么出门。

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

小L想知道，有多少种方案，使得选出来的总喜欢值>M 需要注意，每类物品，至多选择1件，可以不选。

题目描述 小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个的喜欢值是多少。

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

代码

#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
#define int long long
using namespace std;

const int mod=1e9+7,maxn=1e5+5;

int n, m;
int a[maxn];
int v[8][maxn];
int ans;

void dfs(int u, int sum)
{
    //回溯剪枝
    if(sum > m)
    {
        int cnt = 1;
        for(int i = u; i <= n; i++)
            cnt *= (a[i] + 1);
        ans += cnt;
        return;
    }
    if(u == n + 1)  return;
    for(int i = 0; i <= a[u]; i++)
        dfs(u + 1, sum + v[u][i]);
}

signed main()
{
    while(cin >> n >> m)
    {
        ans = 0;
        for(int i = 1; i <= n; i++)
        {
            cin >> a[i];
            for(int j = 1; j <= a[i]; j++)
                cin >> v[i][j];
        }
        dfs(1, 0);
        printf("%lld\n", ans);
    }
}