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

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

推荐阅读

go
2016年10月25日数学考试：斐波那契数列与矩阵快速幂的应用

本次考试于2016年10月25日上午7:50至11:15举行，主要涉及数学专题，特别是斐波那契数列的性质及其在编程中的应用。本文将详细解析考试中的题目，并提供解题思路和代码实现。 ... [详细]

蜡笔小新 2024-12-25 13:08:21
sum
POJ 1691 矩形涂色问题 (DFS/状态压缩DP)

本题通过将每个矩形视为一个节点，根据其相对位置构建拓扑图，并利用深度优先搜索（DFS）或状态压缩动态规划（DP）求解最小涂色次数。本文详细解析了该问题的建模思路与算法实现。 ... [详细]

蜡笔小新 2024-12-25 18:27:21
go
扫描线三巨头 hdu1928hdu 1255 hdu 1542 [POJ 1151]

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

蜡笔小新 2024-12-26 20:04:36
sum
Splay Tree 区间操作优化

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

蜡笔小新 2024-12-26 18:47:12
tree
洛谷 P4116 树上操作：颜色变换与路径查询

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

蜡笔小新 2024-12-26 10:22:20
stream
CUGB图论专题：排水系统中的最大流问题 - EK与Dinic算法解析

本题探讨如何通过最大流算法解决农场排水系统的设计问题。题目要求计算从水源点到汇合点的最大水流速率，使用经典的EK（Edmonds-Karp）和Dinic算法进行求解。 ... [详细]

蜡笔小新 2024-12-25 17:47:23
sum
寻找满足特定条件的整数N的最大和(a+b)

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

蜡笔小新 2024-12-26 19:26:18
tree
Weight the Tree（树形dp）

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

蜡笔小新 2024-12-26 15:55:56
const
使用JPA Criteria API构建动态查询条件

本文介绍如何使用JPA Criteria API创建带有多个可选参数的动态查询方法。当某些参数为空时，这些参数不会影响最终查询结果。 ... [详细]

蜡笔小新 2024-12-26 09:26:16
tree
Codeforces Round #566 (Div. 2) A~F个人题解

Dashboard-CodeforcesRound#566(Div.2)-CodeforcesA.FillingShapes题意：给你一个的表格，你 ... [详细]

蜡笔小新 2024-12-25 18:41:21
version
使用 SQLiteJDBC 和 HikariCP 实现 Java 程序连接 SQLite 数据库

本文介绍了如何通过 Maven 依赖引入 SQLiteJDBC 和 HikariCP 包，从而在 Java 应用中高效地连接和操作 SQLite 数据库。文章提供了详细的代码示例，并解释了每个步骤的实现细节。 ... [详细]

蜡笔小新 2024-12-26 17:34:42
const
Java中访问器与修改器的深入解析

本文详细介绍了Java中的访问器（getter）和修改器（setter），探讨了它们在保护数据完整性、增强代码可维护性方面的重要作用。通过具体示例，展示了如何正确使用这些方法来控制类属性的访问和更新。 ... [详细]

蜡笔小新 2024-12-26 17:25:24
jsp
深入解析 HTTP 500 内部服务器错误

本文详细探讨了HTTP 500内部服务器错误的成因、解决方案及其在Web开发中的影响。通过对具体案例的分析，帮助读者理解并解决此类问题。 ... [详细]

蜡笔小新 2024-12-26 16:55:25
jsp
C++ 中的数组与动态数组初始化

本文探讨了 C++ 中普通数组和标准库类型 vector 的初始化方法。普通数组具有固定长度，而 vector 是一种可扩展的容器，允许动态调整大小。文章详细介绍了不同初始化方式及其应用场景，并提供了代码示例以加深理解。 ... [详细]

蜡笔小新 2024-12-26 15:38:03
join
DLP数据泄露检测原理浅析

最近团队在部署DLP，作为一个技术人员对于黑盒看不到的地方还是充满了好奇心。多次咨询乙方人员DLP的算法原理是什么，他们都以商业秘密为由避而不谈，不得已只能自己查资料学习，于是有了下面的浅见。身为甲方，虽然不需要开发DLP产品，但是也有必要弄明白DLP基本的原理。俗话说工欲善其事必先利其器，只有在懂这个工具的原理之后才能更加灵活地使用这个工具，即使出现意外情况也能快速排错，越接近底层，越接近真相。根据DLP的实际用途，本文将DLP检测分为2部分，泄露关键字检测和近似重复文档检测。 ... [详细]

蜡笔小新 2024-12-25 18:19:32

勋酥-osh海州吴氏

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

Tags | 热门标签

RankList | 热门文章