当前位置: 开发笔记 > 编程语言 > 正文

CodeforcesRound#383(Div.2)D分组背包

作者：勋酥-osh海州吴氏 | 来源：互联网 | 2023-10-17 17:22

给出一群女孩的重量和颜值和她们的朋友关系现在有一个舞台ab是朋友bc是朋友ac就是朋友给出最大承重可以邀请这些女孩来玩对于每一个朋友团体全邀请or邀请一个or不邀请问能邀请的女孩的

给出一群女孩的重量和颜值和她们的朋友关系现在有一个舞台 ab是朋友 bc是朋友 ac就是朋友给出最大承重可以邀请这些女孩来玩

对于每一个朋友团体全邀请or邀请一个or不邀请问能邀请的女孩的最大颜值

比赛的时候一看就是个背包问题似乎在背包九讲上面见过..但是不会写

于是百度.."背包一类选一个"

百度出了分组背包并且第一个搜索结果就是类似于原题的东西..

只不过分组背包的模板是一个or不要加了个bfs 把朋友团体作为一个新朋友加入进这个团体改了改代码..就a了..

虽然fst掉了c...

后来学习了一下发现分组背包是这样写的

for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;)枚举每一个分组

for(int j&＃61;V;j>&＃61;0;j&＃43;&＃43;)枚举背包容量

for(int k&＃61;1;k<&＃61;x;k&＃43;&＃43;)枚举i分组里面的所有物品

dp[j] &＃61; max(dp[j],dp[j-vol[k]]&＃43;val[k]);

当然二维的比较好理解...

在这个题中并查集和bfs统计朋友团体都可以

#include #include #include #include #include #include #include #include using namespace std; #define L long long vectorq[1050]; int val[2050]; int vol[2050]; int dp[1050]; int n,m,w; int id[1050]; vectorz[1050]; void bfs(int u,int cnt){int sumval &＃61; 0;int sumvol &＃61; 0;queueque;que.push(u);id[u] &＃61; cnt;sumval &＃43;&＃61; val[u];sumvol &＃43;&＃61; vol[u];z[cnt].push_back(u);while(!que.empty()){int f&＃61;que.front();que.pop();for(int i&＃61;0;i} int main(){scanf("%d%d%d",&n,&m,&w);for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;)scanf("%d",&vol[i]);for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;)scanf("%d",&val[i]);for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;)q[i].clear();memset(id,-1,sizeof(id));for(int i&＃61;1;i<&＃61;m;i&＃43;&＃43;){int u,v;scanf("%d%d",&u,&v);q[u].push_back(v);q[v].push_back(u);}int cnt &＃61; 0;for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;){if(id[i] &＃61;&＃61; -1){cnt &＃43;&＃43;;z[cnt].clear();bfs(i,cnt);}}memset(dp,0,sizeof(dp));for(int i&＃61;1;i<&＃61;cnt;i&＃43;&＃43;){for(int j&＃61;w;j>&＃61;0;j--){for(int k&＃61;0;k&＃61;vol[d]){if(dp[j]}

转:https://www.cnblogs.com/rayrayrainrain/p/6180982.html

推荐阅读

char
树剖||树链剖分||线段树||BZOJ4034||Luogu3178||[HAOI2015]树上操作

题面：P3178[HAOI2015]树上操作好像其他人都嫌这道题太容易了懒得讲，好吧那我讲。题解：第一个操作和第二个操作本质上是一样的&# ... [详细]

蜡笔小新 2024-11-24 15:06:53
char
HNUOJ 13375 花径问题 (SPFA算法)

本题要求计算从起点到终点所有最短路径的总权重，使用SPFA算法进行求解。 ... [详细]

蜡笔小新 2024-11-25 18:52:54
char
[NOI2012]

来自FallDream的博客，未经允许，请勿转载，谢谢。一天一套noi简直了.昨天勉强做完了noi2011今天教练又丢出来一套noi ... [详细]

蜡笔小新 2024-11-24 17:13:08
char
HDU 2537 键盘输入处理

题目描述了一个名叫Pirates的男孩想要开发一款键盘输入软件，遇到了大小写字母判断的问题。本文提供了该问题的解决方案及实现方法。 ... [详细]

蜡笔小新 2024-11-24 11:01:59
char
Splay 树的高级应用：区间操作详解

在学习了Splay树的基本查找功能后，可能会觉得它与普通的二叉查找树没有太大的区别，仅仅是通过splay操作减少了时间开销。然而，Splay树之所以被誉为“序列之王”，主要在于其强大的区间操作能力。 ... [详细]

蜡笔小新 2024-11-24 06:59:35
char
P3796 AC自动机强化版题解 - Aho-Corasick Algorithm

本文提供了一个关于AC自动机（Aho-Corasick Algorithm）的详细解析与实现方法，特别针对P3796题目进行了深入探讨。文章不仅涵盖了AC自动机的基本概念，还重点讲解了如何通过构建失败指针（fail pointer）来提高字符串匹配效率。 ... [详细]

蜡笔小新 2024-11-23 13:17:52
process
利用Node.js实现PSD文件的高效切图

本文介绍了如何通过Node.js及其psd2json模块，快速实现PSD文件的自动化切图过程，以适应项目中频繁的界面更新需求。此方法不仅提高了工作效率，还简化了从设计稿到实际应用的转换流程。 ... [详细]

蜡笔小新 2024-11-22 13:21:24
process
2022年4月15日算法练习题

2022年4月15日的算法练习题，包括最长公共子序列和线段树的应用。 ... [详细]

蜡笔小新 2024-11-25 19:10:45
config
Skynet 源码解析：启动流程与核心组件

本文详细解析 Skynet 的启动流程，包括配置文件的读取、环境变量的设置、主要线程的启动（如 timer、socket、monitor 和 worker 线程），以及消息队列的实现机制。 ... [详细]

蜡笔小新 2024-11-25 16:23:05
config
利用 Python 和 Scapy 实施 DNS 欺骗攻击的技术解析

本文详细介绍了如何使用 Python 编程语言中的 Scapy 库执行 DNS 欺骗攻击，包括必要的软件安装、攻击流程及代码示例。 ... [详细]

蜡笔小新 2024-11-25 15:52:30
config
深入解析Socket结构与实现

本文详细介绍了Socket在Linux内核中的实现机制，包括基本的Socket结构、协议操作集以及不同协议下的具体实现。通过这些内容，读者可以更好地理解Socket的工作原理。 ... [详细]

蜡笔小新 2024-11-24 12:00:27
config
CodeForces 315B: 线段树与区间更新

题目概述：Sereja 拥有一个由 n 个整数组成的数组 a1, a2, ..., an。他计划执行 m 项操作，这些操作包括更新数组中的特定元素、增加数组中所有元素的值，以及查询数组中的特定元素。 ... [详细]

蜡笔小新 2024-11-23 16:14:08
config
HDU6034 Balala Power!（贪心策略）

题目描述：Balala Power! 时间限制：4000/2000 MS (Java/Other) 内存限制：131072/131072 K (Java/Other)。题目背景及问题描述详见正文。 ... [详细]

蜡笔小新 2024-11-23 15:19:43
jsp
LeetCode 102 - 二叉树层次遍历详解

本文详细解析了LeetCode第102题——二叉树的层次遍历问题，提供了C++语言的实现代码，并对算法的核心思想和具体步骤进行了深入讲解。 ... [详细]

蜡笔小新 2024-11-23 12:14:28
jsp
HihoCoder1398：最大权闭合子图问题解析

本文详细探讨了HihoCoder平台上的1398号问题——最大权闭合子图的求解方法。通过具体实例，深入分析了最大权闭合子图的概念及其算法实现。 ... [详细]

蜡笔小新 2024-11-23 09:31:29

勋酥-osh海州吴氏

这个家伙很懒，什么也没留下！

Tags | 热门标签

RankList | 热门文章