搜索的优化

题目描述
小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

思路：
对搜索进行优化 当满足情况的时候 后面的选择都不影响最后结果大于m的结果，通过高中数学的排列组合思想，将结果数相乘即可。

#include<iostream>
#include<queue>
#include<vector> 
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
//--------------------------------------
int  k, m;
long long ans;

//--------------------------------------

int arrSize[10];
int arr[10][105];
void dfs(int step, int sum)
{

    //搜索的优化

    if (sum > m)//不管结果如何 
    {
        ll re = 1;
        //如果已经是最后一个了 直接会加到答案里面
        for (int i = step; i < k; i++)
        {
            re *=( arrSize[i]+1);//把数目相乘即可 记得把0乘上
          }
        ans += re;
        return;
    }
    if (step == k)//已经选完了 用来控制搜索的终止
    {
        return;
    }
    for (int i = 0; i <= arrSize[step]; i++)//把0 也包括进去 
    {
        dfs(step + 1, sum + arr[step][i]);
    }
}
int main()
{
    while (cin >> k >> m)
    {
        ans = 0;
        for (int i = 0; i < k; i++)//深度从0开始
        {
            cin >> arrSize[i];
            for (int j = 1; j <= arrSize[i]; j++)//第0个当做是不选的情况
            {
                cin >> arr[i][j];
            }
        }
        dfs(0, 0);
        cout << ans << endl;
    }
}
/*
4 1
2 2 2
2 2 2
3 2 2 2
5 2 2 2 2 2

*/