热门标签 | 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



推荐阅读
  • 本文主要解析了Open judge C16H问题中涉及到的Magical Balls的快速幂和逆元算法,并给出了问题的解析和解决方法。详细介绍了问题的背景和规则,并给出了相应的算法解析和实现步骤。通过本文的解析,读者可以更好地理解和解决Open judge C16H问题中的Magical Balls部分。 ... [详细]
  • HDU 2372 El Dorado(DP)的最长上升子序列长度求解方法
    本文介绍了解决HDU 2372 El Dorado问题的一种动态规划方法,通过循环k的方式求解最长上升子序列的长度。具体实现过程包括初始化dp数组、读取数列、计算最长上升子序列长度等步骤。 ... [详细]
  • 本文讨论了使用差分约束系统求解House Man跳跃问题的思路与方法。给定一组不同高度,要求从最低点跳跃到最高点,每次跳跃的距离不超过D,并且不能改变给定的顺序。通过建立差分约束系统,将问题转化为图的建立和查询距离的问题。文章详细介绍了建立约束条件的方法,并使用SPFA算法判环并输出结果。同时还讨论了建边方向和跳跃顺序的关系。 ... [详细]
  • 本文介绍了P1651题目的描述和要求,以及计算能搭建的塔的最大高度的方法。通过动态规划和状压技术,将问题转化为求解差值的问题,并定义了相应的状态。最终得出了计算最大高度的解法。 ... [详细]
  • 3.223.28周学习总结中的贪心作业收获及困惑
    本文是对3.223.28周学习总结中的贪心作业进行总结,作者在解题过程中参考了他人的代码,但前提是要先理解题目并有解题思路。作者分享了自己在贪心作业中的收获,同时提到了一道让他困惑的题目,即input details部分引发的疑惑。 ... [详细]
  • 如何自行分析定位SAP BSP错误
    The“BSPtag”Imentionedintheblogtitlemeansforexamplethetagchtmlb:configCelleratorbelowwhichi ... [详细]
  • VScode格式化文档换行或不换行的设置方法
    本文介绍了在VScode中设置格式化文档换行或不换行的方法,包括使用插件和修改settings.json文件的内容。详细步骤为:找到settings.json文件,将其中的代码替换为指定的代码。 ... [详细]
  • 本文介绍了一个在线急等问题解决方法,即如何统计数据库中某个字段下的所有数据,并将结果显示在文本框里。作者提到了自己是一个菜鸟,希望能够得到帮助。作者使用的是ACCESS数据库,并且给出了一个例子,希望得到的结果是560。作者还提到自己已经尝试了使用"select sum(字段2) from 表名"的语句,得到的结果是650,但不知道如何得到560。希望能够得到解决方案。 ... [详细]
  • CF:3D City Model(小思维)问题解析和代码实现
    本文通过解析CF:3D City Model问题,介绍了问题的背景和要求,并给出了相应的代码实现。该问题涉及到在一个矩形的网格上建造城市的情景,每个网格单元可以作为建筑的基础,建筑由多个立方体叠加而成。文章详细讲解了问题的解决思路,并给出了相应的代码实现供读者参考。 ... [详细]
  • 也就是|小窗_卷积的特征提取与参数计算
    篇首语:本文由编程笔记#小编为大家整理,主要介绍了卷积的特征提取与参数计算相关的知识,希望对你有一定的参考价值。Dense和Conv2D根本区别在于,Den ... [详细]
  • 成功安装Sabayon Linux在thinkpad X60上的经验分享
    本文分享了作者在国庆期间在thinkpad X60上成功安装Sabayon Linux的经验。通过修改CHOST和执行emerge命令,作者顺利完成了安装过程。Sabayon Linux是一个基于Gentoo Linux的发行版,可以将电脑快速转变为一个功能强大的系统。除了作为一个live DVD使用外,Sabayon Linux还可以被安装在硬盘上,方便用户使用。 ... [详细]
  • [大整数乘法] java代码实现
    本文介绍了使用java代码实现大整数乘法的过程,同时也涉及到大整数加法和大整数减法的计算方法。通过分治算法来提高计算效率,并对算法的时间复杂度进行了研究。详细代码实现请参考文章链接。 ... [详细]
  • C++中的三角函数计算及其应用
    本文介绍了C++中的三角函数的计算方法和应用,包括计算余弦、正弦、正切值以及反三角函数求对应的弧度制角度的示例代码。代码中使用了C++的数学库和命名空间,通过赋值和输出语句实现了三角函数的计算和结果显示。通过学习本文,读者可以了解到C++中三角函数的基本用法和应用场景。 ... [详细]
  • 本文介绍了一个题目的解法,通过二分答案来解决问题,但困难在于如何进行检查。文章提供了一种逃逸方式,通过移动最慢的宿管来锁门时跑到更居中的位置,从而使所有合格的寝室都居中。文章还提到可以分开判断两边的情况,并使用前缀和的方式来求出在任意时刻能够到达宿管即将锁门的寝室的人数。最后,文章提到可以改成O(n)的直接枚举来解决问题。 ... [详细]
  • 本文讨论了如何使用IF函数从基于有限输入列表的有限输出列表中获取输出,并提出了是否有更快/更有效的执行代码的方法。作者希望了解是否有办法缩短代码,并从自我开发的角度来看是否有更好的方法。提供的代码可以按原样工作,但作者想知道是否有更好的方法来执行这样的任务。 ... [详细]
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社区 版权所有