热门标签 | HotTags
当前位置:  开发笔记 > 编程语言 > 正文

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

给出一群女孩的重量和颜值和她们的朋友关系现在有一个舞台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



推荐阅读
  • DNN Community 和 Professional 版本的主要差异
    本文详细解析了 DotNetNuke (DNN) 的两种主要版本:Community 和 Professional。通过对比两者的功能和附加组件,帮助用户选择最适合其需求的版本。 ... [详细]
  • 本文将介绍如何编写一些有趣的VBScript脚本,这些脚本可以在朋友之间进行无害的恶作剧。通过简单的代码示例,帮助您了解VBScript的基本语法和功能。 ... [详细]
  • golang常用库:配置文件解析库/管理工具viper使用
    golang常用库:配置文件解析库管理工具-viper使用-一、viper简介viper配置管理解析库,是由大神SteveFrancia开发,他在google领导着golang的 ... [详细]
  • 技术分享:从动态网站提取站点密钥的解决方案
    本文探讨了如何从动态网站中提取站点密钥,特别是针对验证码(reCAPTCHA)的处理方法。通过结合Selenium和requests库,提供了详细的代码示例和优化建议。 ... [详细]
  • 本文详细介绍了如何在Linux系统上安装和配置Smokeping,以实现对网络链路质量的实时监控。通过详细的步骤和必要的依赖包安装,确保用户能够顺利完成部署并优化其网络性能监控。 ... [详细]
  • 本文详细介绍了 Dockerfile 的编写方法及其在网络配置中的应用,涵盖基础指令、镜像构建与发布流程,并深入探讨了 Docker 的默认网络、容器互联及自定义网络的实现。 ... [详细]
  • Python自动化处理:从Word文档提取内容并生成带水印的PDF
    本文介绍如何利用Python实现从特定网站下载Word文档,去除水印并添加自定义水印,最终将文档转换为PDF格式。该方法适用于批量处理和自动化需求。 ... [详细]
  • Docker的安全基准
    nsitionalENhttp:www.w3.orgTRxhtml1DTDxhtml1-transitional.dtd ... [详细]
  • QUIC协议:快速UDP互联网连接
    QUIC(Quick UDP Internet Connections)是谷歌开发的一种旨在提高网络性能和安全性的传输层协议。它基于UDP,并结合了TLS级别的安全性,提供了更高效、更可靠的互联网通信方式。 ... [详细]
  • Explore how Matterverse is redefining the metaverse experience, creating immersive and meaningful virtual environments that foster genuine connections and economic opportunities. ... [详细]
  • 1.如何在运行状态查看源代码?查看函数的源代码,我们通常会使用IDE来完成。比如在PyCharm中,你可以Ctrl+鼠标点击进入函数的源代码。那如果没有IDE呢?当我们想使用一个函 ... [详细]
  • 题目描述:给定n个半开区间[a, b),要求使用两个互不重叠的记录器,求最多可以记录多少个区间。解决方案采用贪心算法,通过排序和遍历实现最优解。 ... [详细]
  • 深入理解Java中的volatile、内存屏障与CPU指令
    本文详细探讨了Java中volatile关键字的作用机制,以及其与内存屏障和CPU指令之间的关系。通过具体示例和专业解析,帮助读者更好地理解多线程编程中的同步问题。 ... [详细]
  • 前言--页数多了以后需要指定到某一页(只做了功能,样式没有细调)html ... [详细]
  • 360SRC安全应急响应:从漏洞提交到修复的全过程
    本文详细介绍了360SRC平台处理一起关键安全事件的过程,涵盖从漏洞提交、验证、排查到最终修复的各个环节。通过这一案例,展示了360在安全应急响应方面的专业能力和严谨态度。 ... [详细]
author-avatar
勋酥-osh海州吴氏
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有