首页 > 选择困难症
开通博客写题解
头像 shyyhs
发表于 2020-07-11 18:20:23
教我***儿子做题.https://www.acwing.com/problem/content/173/ 这个题的思路和这个题目是类似的.我们可以先进行排序,预处理k/2的种类存入一个数组..然后另外一半再进行dfs.这种做法很优但是对于这个题目来说.因为数据水,就不至于,但是还是写下. #inc 展开全文
去ta的博客 赞 (6) 回复(0) 收起
头像 ouk
发表于 2020-08-13 16:52:14
题目描述小L有严重的选择困难症。早上起床后，需要花很长时间决定今天穿什么出门。假设一共有k类物品需要搭配选择，每类物品的个数为Ai，每个物品有一个喜欢值Vj，代表小L对这件物品的喜欢程度。小L想知道，有多少种方案，使得选出来的总喜欢值>M需要注意，每类物品，至多选择1件，可以不选。 输入描述: 展开全文
去ta的博客 赞 (4) 回复(0) 收起
头像 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 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 cheese_case
发表于 2022-01-27 11:15:20
感觉这题dp不错，尤其是对于剪枝得思考 应该挺常用，先说说我对于dfs得感受:对于每一层得所有可能都要考虑，然后进入下一层即可，对于此题每一层得所有可能即是 当前step选哪一个/不选，对于具体细节请看注释 ">using namespace std; typedef long long ll; v 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 nchu_py
发表于 2022-03-29 18:32:39
题目描述 小L有严重的选择困难症。 早上起床后，需要花很长时间决定今天穿什么出门。 假设一共有k类物品需要搭配选择，每类物品的个数为Ai，每个物品有一个喜欢值Vj，代表小L对这件物品的喜欢程度。 小L想知道，有多少种方案，使得选出来的总喜欢值>M 需要注意，每类物品，至多选择1件，可以不选。 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 coder+9
发表于 2021-12-09 09:35:09
我只想到了朴素方法，膜拜楼下大佬的剪枝思路，蛮快的。 if(res>m){ ll re=1; for(int j = i;j<k;j++){ re*=(asize[j]+1);//注意加上没有拿该物品的情况 } 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 A_normal_man
发表于 2022-09-14 16:51:30
dfs搜索，通过>M这个条件进行剪枝， 先对每类物品的数组进行排序，如果在某个节点已经大于M的时候，以下的分支的个数都可以用乘法得出。 #include<iostream> #include<algorithm> using namespace std; int k, 展开全文
去ta的博客 赞 (0) 回复(0) 收起
查看本题
查看本题讨论

相关比赛

等你来战

查看全部
牛客竞赛，专业的竞技算法训练平台

扫描二维码，进入QQ群

扫码关注“比赛自动姬”