链的独立集题目描述 给定 n 个数字构成的序列 a1​,a2​,a3​,…,an​，请从中挑选一些数字构成一个独立集。所谓独立集就是原数列的一部分数字，且这些数字在原数列中均不相邻。找出数字之和最大的

目录

  1. 1题目信息
  2. 2题目题干
  3. 3答案解析
  4. 4相关题目
  1. 5提示声明
  2. 6猜你喜欢
  3. 7加入收藏
  4. 8我要纠错

题目信息

题目类型
练习
题目年份
2024
题目题型
编程题
关 键 词
链的独立集 上海计算机学会 2024年10月月赛乙组题解

题目题干

题目描述MM3100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
给定 n 个数字构成的序列 a1​,a2​,a3​,…,an​，请从中挑选一些数字构成一个独立集。所谓独立集就是原数列的一部分数字，且这些数字在原数列中均不相邻。找出数字之和最大的独立集，输出这些数字的和。注意若数字都是负数，可以不挑任何数，此时输出 0。MM3100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
MM3100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
输入格式MM3100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
第一行：单个整数 nMM3100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
第二行：n 个整数 a1​,a2​,…,an​MM3100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
输出格式MM3100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
单个整数：表示最大的独立集MM3100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
数据范围MM3100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
对于 30% 的数据，1≤n≤20；MM3100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
对于 60% 的数据，1≤n≤3,000；MM3100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
对于 100% 的数据，1≤n≤100,000；MM3100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
−10000≤ai​≤10000MM3100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
样例数据MM3100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
 输入:MM3100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
5MM3100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
10 20 30 -10 3MM3100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
输出:MM3100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
43MM3100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
 

答案解析

相关题目

子集和题目描述 给定 n 个数字 a1​,a2​,…,an​，请判断能否这从这些数字中挑选一些数字，使得它们的和等于一个给定的整数 t？ 输入格式 第一行：单个整数 n 第二行：n 个整数 a1​,
链的独立集题目描述 给定 n 个数字构成的序列 a1​,a2​,a3​,…,an​，请从中挑选一些数字构成一个独立集。所谓独立集就是原数列的一部分数字，且这些数字在原数列中均不相邻。找出数字之和最大的
重合线段题目描述 Carol 有 n 条线段，从 1 到 n 编号，第 ii 条覆盖数轴上[Li​,Ri​] 的区间。 Carol 认为一条线段如果去掉之后，剩余线段的并集和先前没有差别，那这条线段
最小差异题目描述 　　Bob 有 n 个数对，第 i 个是 (ai​,bi​)，同时有两个桶，初始都为空。 　　Bob 会对于i=1,2,⋯,n，依次选择 ai​,bi​ 中的恰好一个，并任意加入
放置小球题目描述 小球有从 1 到 m共 m 种不同的颜色，Alice 有 ai​ 个第 i种颜色的小球和 n个空盒子。 如果每个球都放进了一个盒子，并且每个盒子内所有球都不同色，那么这个放置小球的
线段数题目描述 给定数组 a=[a1​,a2​,⋯,an​]，Eve 可以执行任意次（可能 0 次）以下操作： 选择1≤i≤n，令 ai​←ai​+1。 Eve 希望最终数组中任意三个相邻元素之和都
添加删除题目描述 有 n 个小球，第 i个小球上写着一个数字ai​ 代表它的分数。对于一个固定的参数 m（1≤m≤n）可以进行如下游戏：Dave 初始分数为 0，把第 1∼(m−1) 个小球先放进一
考勤系统题目描述 在 Carol 的办公楼的入口处有一套刷卡系统，每个员工都有一张唯一的身份卡，他们每次进出大楼都要刷卡，而系统会依次记录每次刷卡的员工编号，员工和他的编号一一对应，且在一天内一共有 
大胃王题目描述 Bob 的同事向 Bob 发出了大胃王挑战：“如果你吃了超过 x 个包子，那你每多吃一个，我就给你 5元。“ 例如，如果 x=5且 Bob 吃了 8个包子，那么他会收到 15 元，因
棋盘距离题目描述 在一个棋盘上，有两颗棋子，一颗棋子在第 a 行第 b 列，另一个颗棋子在第 x行第 y列。 每一步，可以选择一个棋子沿行方向移动一个单位，或沿列方向移动一个单位，或同时沿行方向及列方

提示声明

  • 免责声明：本站资源均来自网络或者用户投稿，仅供用于学习和交流：如有侵权联系删除!
  • 温馨提示：本文属于积分文章，需要充值获得积分或升级VIP会员，也可在会员中心投稿获取。

猜你喜欢

  • ©2016-2021 100150.com
  • 一个专注于青少年科技类考级、竞赛题库的网站
  • 提供电子学会python等级考试练习，C语言等级考试真题，
  • 蓝桥杯竞赛真题，信息学奥赛NOIP CSP-J/S真题等
  • 沪ICP备19038360号-4