选择困难症（DFS）

题目：

小L有严重的选择困难症。
早上起床后，需要花很长时间决定今天穿什么出门。
假设一共有k类物品需要搭配选择，每类物品的个数为Ai，每个物品有一个喜欢值Vj，代表小L对这件物品的喜欢程度。
小L想知道，有多少种方案，使得选出来的总喜欢值>M
需要注意，每类物品，至多选择1件，可以不选。

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

输入
2 5
3 1 3 4
2 2 3
2 1
2 2 2
2 2 2

输出
3

8

题解：简单题意就是在每类物品中选一种或不选，计算出总喜欢值大于目标值的个数。首先看到数据量可以直接想到dfs，其次再开好个long long，不然直接没掉。
法一：实现思路就是每一次遍历该类物品的一种，该类物品遍历完之后（递归回来），再有一种选择就是不遍历这类物品，直接遍历下一类物品，但是这样不进行剪枝会Tle，所以可以进行一个剪枝，可以先将每一类物品的喜欢值进行从小到大排序（其实不排也行，只是排了更加优化一些），然后当选完该类物品的其中一个后，接着选下一类物品时，总的喜欢值已经超过目标值，那么此时可以将剩下所有类物品进行组合，也就是剩下的每一类物品数量 + 1然后相乘即可，+1：因为可以不选择该类物品。

法二：双向dfs（占坑）...

AC代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
int k, m;
LL a[10][105];
LL flagA[10], num = 0;

void dfs(int f, int cnt)
{
	if(cnt > m) //最优化剪枝 
	{
		LL temp = 1;
		for(int i = f; i <= k; i++) //剩下数所有的方案 
			temp *= (flagA[i] + 1);
		num += temp;
		return;
	}
	if(f > k)
		return;
	for(int i = 1; i <= flagA[f]; i++) //遍历列 
	{
		dfs(f + 1, cnt + a[f][i]);
		//dfs(x + 1, i, f + 1, cnt);
	}
	dfs(f + 1, cnt);
}

int main()
{
	ios::sync_with_stdio(false);
	//freopen("cin.in", "r", stdin);
	//freopen("cout.out", "w", stdout);
	while(cin >> k >> m)
	{
		memset(a, 0 ,sizeof(a));
		memset(flagA, 0 ,sizeof(flagA));
		for(int i = 1; i <= k; i++)
		{
			cin >> flagA[i];
			for(int j = 1; j <= flagA[i]; j++)
				cin >> a[i][j];
			//sort(a[i] + 1, a[i] + flagA[i] + 1);
		}
		dfs(1, 0);
		cout << num << endl;
		num = 0;
	}
	return 0;
}

选择困难症（DFS）

原文：https://www.cnblogs.com/K2MnO4/p/13817639.html