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

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

推荐阅读

io
CUGB图论专题：排水系统中的最大流问题 - EK与Dinic算法解析

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

蜡笔小新 2024-12-25 17:47:23
bit
Splay Tree 区间操作优化

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

蜡笔小新 2024-12-26 18:47:12
io
2016年10月25日数学考试：斐波那契数列与矩阵快速幂的应用

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

蜡笔小新 2024-12-25 13:08:21
io
UNP 第9章：主机名与地址转换

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

蜡笔小新 2024-12-27 11:26:39
io
扫描线三巨头 hdu1928hdu 1255 hdu 1542 [POJ 1151]

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

蜡笔小新 2024-12-26 20:04:36
io
寻找满足特定条件的整数N的最大和(a+b)

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

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

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

蜡笔小新 2024-12-26 10:22:20
io
企业级项目中 Webpack 配置优化指南

本文详细介绍了在企业级项目中如何优化 Webpack 配置，特别是在 React 移动端项目中的最佳实践。涵盖资源压缩、代码分割、构建范围缩小、缓存机制以及性能优化等多个方面。 ... [详细]

蜡笔小新 2024-12-24 14:41:48
io
编写有趣的VBScript恶作剧脚本

本文将介绍如何编写一些有趣的VBScript脚本，这些脚本可以在朋友之间进行无害的恶作剧。通过简单的代码示例，帮助您了解VBScript的基本语法和功能。 ... [详细]

蜡笔小新 2024-12-28 09:46:23
io
使用Objective-C和dispatch库实现并发素数计算

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

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

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

蜡笔小新 2024-12-27 16:20:10
const
组合数学问题：棋盘上的组合数计算

本文探讨了如何在模运算下高效计算组合数C(n, m)，并详细介绍了乘法逆元的应用。通过扩展欧几里得算法求解乘法逆元，从而实现除法取余的计算。 ... [详细]

蜡笔小新 2024-12-26 21:41:44
io
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
io
2-SAT问题学习笔记

本文介绍了一种解决二元可满足性（2-SAT）问题的方法。通过具体实例，详细解释了如何构建模型、应用算法，并提供了编程实现的细节和优化建议。 ... [详细]

蜡笔小新 2024-12-24 21:48:43
io
Tetris 排名系统 (拓扑排序与并查集的应用)

本题旨在通过给定的评级信息，利用拓扑排序和并查集算法来确定全球 Tetris 高手排行榜。题目要求判断是否可以根据提供的信息生成一个明确的排名表，或者是否存在冲突或信息不足的情况。 ... [详细]

蜡笔小新 2024-12-24 21:03:51

勋酥-osh海州吴氏

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

Tags | 热门标签

RankList | 热门文章