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

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

推荐阅读

java
寻找满足特定条件的整数N的最大和(a+b)

本文探讨了如何在给定整数N的情况下，找到两个不同的整数a和b，使得它们的和最大，并且满足特定的数学条件。 ... [详细]

蜡笔小新 2024-12-26 19:26:18
case
扫描线三巨头 hdu1928hdu 1255 hdu 1542 [POJ 1151]

学习链接：http:blog.csdn.netlwt36articledetails48908031学习扫描线主要学习的是一种扫描的思想，后期可以求解很 ... [详细]

蜡笔小新 2024-12-26 20:04:36
数组
Weight the Tree（树形dp）

题目Link题目学习link1题目学习link2题目学习link3%%%受益匪浅！－－－－－&# ... [详细]

蜡笔小新 2024-12-26 15:55:56
go
洛谷 P4116 树上操作：颜色变换与路径查询

本题涉及一棵由N个节点组成的树（共有N-1条边），初始时所有节点均为白色。题目要求处理两种操作：一是改变某个节点的颜色（从白变黑或从黑变白）；二是查询从根节点到指定节点路径上的第一个黑色节点，若无则输出-1。 ... [详细]

蜡笔小新 2024-12-26 10:22:20
byte
golang常用库：配置文件解析库/管理工具viper使用

golang常用库：配置文件解析库管理工具-viper使用-一、viper简介viper配置管理解析库，是由大神SteveFrancia开发，他在google领导着golang的 ... [详细]

蜡笔小新 2024-12-28 13:47:52
join
技术分享：从动态网站提取站点密钥的解决方案

本文探讨了如何从动态网站中提取站点密钥，特别是针对验证码（reCAPTCHA）的处理方法。通过结合Selenium和requests库，提供了详细的代码示例和优化建议。 ... [详细]

蜡笔小新 2024-12-28 04:11:47
go
USACO 2014 Jan - Moolympics区间记录优化算法

题目描述：给定n个半开区间[a, b)，要求使用两个互不重叠的记录器，求最多可以记录多少个区间。解决方案采用贪心算法，通过排序和遍历实现最优解。 ... [详细]

蜡笔小新 2024-12-27 18:14:31
go
Splay Tree 区间操作优化

本文详细介绍了使用Splay Tree进行区间操作的实现方法，包括插入、删除、修改、翻转和求和等操作。通过这些操作，可以高效地处理动态序列问题，并且代码实现具有一定的挑战性，有助于编程能力的提升。 ... [详细]

蜡笔小新 2024-12-26 18:47:12
case
使用Objective-C和dispatch库实现并发素数计算

本文介绍如何使用Objective-C结合dispatch库进行并发编程，以提高素数计数任务的效率。通过对比纯C代码与引入并发机制后的代码，展示dispatch库的强大功能。 ... [详细]

蜡笔小新 2024-12-28 08:44:35
list
MyBatis 动态 SQL 详解与应用

本文深入探讨 MyBatis 中动态 SQL 的使用方法，包括 if/where、trim 自定义字符串截取规则、choose 分支选择、封装查询和修改条件的 where/set 标签、批量处理的 foreach 标签以及内置参数和 bind 的用法。 ... [详细]

蜡笔小新 2024-12-27 16:20:10
case
深入解析 MVC 源码：ParameterDescriptor 与 Action 方法参数绑定

在前两篇文章中，我们探讨了 ControllerDescriptor 和 ActionDescriptor 这两个描述对象，分别对应控制器和操作方法。本文将基于 MVC3 源码进一步分析 ParameterDescriptor，即用于描述 Action 方法参数的对象，并详细介绍其工作原理。 ... [详细]

蜡笔小新 2024-12-27 15:26:10
数组
UNP 第9章：主机名与地址转换

本章探讨了用于在主机名和数值地址之间进行转换的函数，如gethostbyname和gethostbyaddr。此外，还介绍了getservbyname和getservbyport函数，用于在服务器名和端口号之间进行转换。 ... [详细]

蜡笔小新 2024-12-27 11:26:39
case
HTML Attribute Naming Conventions for Fast Components

This document outlines the recommended naming conventions for HTML attributes in Fast Components, focusing on readability and consistency with existing standards. ... [详细]

蜡笔小新 2024-12-26 19:13:45
tree
长春大学软件工程：二叉排序树实验报告

本实验主要探讨了二叉排序树（BST）的基本操作，包括创建、查找和删除节点。通过具体实例和代码实现，详细介绍了如何使用递归和非递归方法进行关键字查找，并展示了删除特定节点后的树结构变化。 ... [详细]

蜡笔小新 2024-12-26 15:32:56
list
VxWorks中的双向链表与环形缓冲应用

本文详细探讨了VxWorks操作系统中双向链表和环形缓冲区的实现原理及使用方法，通过具体示例代码加深理解。 ... [详细]

蜡笔小新 2024-12-26 13:26:16

勋酥-osh海州吴氏

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

Tags | 热门标签

RankList | 热门文章