选择困难症

[编程题]选择困难症

热度指数：45 时间限制：C/C++ 3秒，其他语言6秒空间限制：C/C++ 128M，其他语言256M
算法知识视频讲解

小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

输入

输出

3
8

算法知识视频讲解

shyyhs

发表于 2020-07-11 18:20:23

教我***儿子做题.https://www.acwing.com/problem/content/173/ 这个题的思路和这个题目是类似的.我们可以先进行排序,预处理k/2的种类存入一个数组..然后另外一半再进行dfs.这种做法很优但是对于这个题目来说.因为数据水,就不至于,但是还是写下. #inc 展开全文

ouk

发表于 2020-08-13 16:52:14

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

cheese_case

发表于 2022-01-27 11:15:20

感觉这题dp不错，尤其是对于剪枝得思考应该挺常用，先说说我对于dfs得感受:对于每一层得所有可能都要考虑，然后进入下一层即可，对于此题每一层得所有可能即是当前step选哪一个/不选，对于具体细节请看注释 ">using namespace std; typedef long long ll; v 展开全文

KaitoKID

发表于 2025-05-02 20:10:03

先上代码： #define MX 10 #define NX 200 using namespace std; int a[MX + 10],p[MX + 10][NX + 10]; long long t[1000000 + 10]; int k,M; long long ans,cnt,b; i 展开全文