题目链接 最大学分 题目描述 有  门课程和  个选课名额。每门课程  有一个学分  和至多一门直接先修课 。如果  则表示没有先修课。选修一门课程必须先选修其所有的先修课程（即所有祖先课程）。 你需要从  门课程中恰好选出  门，要求满足所有先修课约束，并使得所选课程的总学分最大。 输入:  第一行输入两个整数 ，分别表示课程总数与需选课程数。 接下来  行，每行输入两个整数 ，分别表示第  门课程的先修课和学分。  输出:  输出一个整数，代表能取得的最大学分。  解题思路 这个问题的本质是在一个森林结构的依赖关系上，选择固定数量的节点，以获取最大权重。这是一个典型的树形DP问题，并结合了...

题目链接 来硬的 题目描述 有  枚煤炭和  单位的铁矿石。第  枚煤炭可以融化  单位的铁矿石，燃烧时间为  秒。 你拥有一项魔法，至多可以对一枚煤炭施放，将其升级。若第  枚煤炭被升级，它的融化量变为 ，燃烧时间变为 。 你需要计算出将所有  单位铁矿石烧炼完毕所需的最短时间。 输入:  第一行输入两个整数 ，分别表示煤炭数量与铁矿石总量。() 接下来  行，每行输入两个整数  ( 可达 )。  输出:  输出一个整数，表示烧炼完所有铁矿石所需的最短时间。  解题思路 本题的数据范围 ( 和  很大, 但 ) 是解题的关键。直接使用常规背包DP会导致内存超限。正确的思路是分情况讨论：   ...

题目链接 【模板】分组背包 题目描述 给定  件物品和一个最大可承重为  的背包。所有物品被划分为若干个组，同一组中的物品是互斥的，即每组至多只能选择一件物品。 第  件物品的重量是 ，价值是 ，所属组别是 。 求解在不超过背包承重的前提下，选择若干物品使得总价值最大。 输入:  第一行输入两个整数 ，分别表示物品数量与背包容量。 接下来  行，每行输入三个整数 ，描述第  件物品的重量、价值与所属组别。  输出:  输出一个整数，代表在约束条件下可以获得的最大价值。  解题思路 本题是典型的 分组背包问题。其核心特点是：所有物品被分成若干组，每组内的物品相互冲突，最多只能选一个。   问题转...

题目链接 【模板】二维费用背包 题目描述 小红有  个事件可以分享。对于第  个事件，分享需要花费  分钟时间和  点精力，并能获得  点快乐值。小红希望在总耗时不超过 ，总消耗精力不超过  的前提下，选择分享若干事件，使得获得的快乐值总和最大。 输入:  第一行输入一个整数 ，表示事件数量。 第二行输入两个整数  和 ，表示可用时间和可用精力的上限。 接下来  行，每行输入三个整数 ，描述第  个事件的参数。  输出:  输出一个整数，代表在限制条件内能获得的最大快乐值。  解题思路 本题是一个典型的 二维费用01背包问题。与传统的01背包问题不同，这里每个物品（事件）有两个“费用”或“成本...

题目链接 【模板】多重背包 题目描述 给定  种物品和一个容量为  的背包。第  种物品的体积是 ，价值是 ，并且数量最多有  件。求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。 输入:  第一行输入一个整数 ，表示有  组测试数据。 对于每组测试数据：  第一行输入两个整数 ，分别表示物品种类和背包容量。 接下来  行，每行输入三个整数 ，分别表示第  种物品的体积、价值和数量。    输出:  对于每组测试数据，输出一个整数，表示能获得的最大总价值。  解题思路 本题是典型的 多重背包问题。它介于01背包和完全背包之间：每种物品可以选择多次，但有数量上限。   ...

题目链接 【模板】完全背包 题目描述 给定  种物品和一个容量为  的背包。第  种物品的体积是 ，价值是 。每种物品都有无限件可用。求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。 输入:  第一行输入一个整数 ，表示有  组测试数据。 对于每组测试数据：  第一行输入两个整数 ，分别表示物品数量和背包容量。 接下来  行，每行输入两个整数 ，分别表示第  件物品的体积和价值。    输出:  对于每组测试数据，输出一个整数，表示能获得的最大总价值。  解题思路 本题是典型的 完全背包问题 模型。与01背包问题不同的是，每种物品可以选取无限次。我们可以使用动态规划来...

题目链接 山脉突起度分析 题目描述 给定一个由非负整数组成的海拔数组 。一个“山脉区间”  被定义为存在一个峰顶索引  ()，使得  单调非递减，且  单调非递增。 一个有效的山脉区间必须包含严格的上升和下降部分，这由条件  且  来保证。 每个有效山脉区间的“突起度”  定义为峰顶海拔与区间两端点海拔较低者的差值：。 任务是找到所有可能的“山脉区间”中，最大的那个“突起度”。 输入:  第一行：数据点数量 。 第二行： 个海拔高度 。  输出:  一个整数，代表最大的突起度。若不存在有效的山脉区间，则为 。  解题思路 这是一个寻找最优子结构的问题。暴力枚举所有可能的区间起点 、终点  和峰...

题目链接 星际舰队的补给分配 题目描述 一支星际舰队需要进行能量分配。补给舰队列  按顺序提供能量，作战舰队列  按顺序接收能量。整个流程遵循一套特定的分配规则，直到补给舰用完或作战舰全部满足需求。任务是计算最终有多少艘作战舰未能获得补给。 设当前补给舰的能量为 ，作战舰队列队首的需求为 。 分配规则如下：  精准匹配 ()：补给舰的能量刚好满足队首作战舰。两者都出队。 超量分配 ()：补给舰的能量超额。寻找一个最大的 ，使得队首  艘作战舰的总需求 。这  艘作战舰和该补给舰都出队。 需求不足 ()：补给舰能量不足。队首作战舰放弃本次机会，移动到队列末尾。该补给舰继续尝试为新的队首作战舰进行...

题目链接 星际商人的贸易之旅 题目描述 一位星际商人拥有初始宇宙信用点 ，计划进行为期  天的贸易活动。空间站中有  种商品，第  种商品的购买成本为 ，纯利润为 。 贸易规则如下：  每日一易：每天最多购买一件商品。 资金约束：购买商品时，当前信用点必须不低于其成本。 即时交易：购买后立即贩卖，信用点更新为 。 商品唯一：每种商品只有一件。  任务是规划  天的贸易，最大化总利润。 输入:  第一行：贸易天数 。 第二行：初始信用点 。 第三行： 种商品的成本数组 。 第四行： 种商品的利润数组 。  输出:  一个整数，代表能赚取的最大总利润。  解题思路 这是一个典型的贪心问题。我们的目...

题目链接 炼金术士的药剂平衡 题目描述 两位炼金术士各有  种魔法材料，其魔力值分别由数组  和  表示。当两个数组在排序后完全相同时，称之为完美平衡。 他们可以执行“置换术”：交换一个来自  的材料和一个来自  的材料。每次操作的法力消耗为被交换的两种材料魔力值中的较小者，即 。 任务是计算达成完美平衡所需的最小总法力。如果无法达到平衡，则输出 -1。 输入:  第一行是材料数量 。 第二行是数组  的  个整数。 第三行是数组  的  个整数。  输出:  一个整数，代表最小总法力消耗。  解题思路 这是一个复杂的贪心问题。核心在于，除了直接交换两个釜中多余的材料，我们还可以利用一个全局最...

题目链接 时空漫游者的能量跳跃 题目描述 一位时空漫游者需要从路径的起点信标  跳跃到终点信标 。路径上共有  个信标，每个信标  拥有能量值 。 漫游者从信标  出发，下一步可以跳跃到区间  内的任意一个信标，其中  是最大跳跃距离。 任务是规划一条从信标  到信标  的路径，使得收集到的总能量最大化。 输入:  第一行是最大跳跃距离 。 第二行是信标总数 。 第三行是  个整数，代表每个信标的能量值 。  输出:  一个整数，代表能收集到的最大总能量。  解题思路 这是一个典型的动态规划问题，旨在寻找一条最优路径以获得最大累积值。 状态定义 我们定义一个数组 ，其中  表示跳跃到第  个信...

题目链接 星尘轨迹分析 题目描述 分析一批天体观测数据，数据格式为 id t，其中  是天体标识符， 是观测时间戳。数据已按时间戳  升序排列。 定义“观测间隔”为某次观测与前一次观测的时间差。对于任务的第一次观测，其观测间隔为该次观测的时间戳与  的差。 任务是找出产生最短观测间隔和最长观测间隔的天体 。如果多个天体的观测间隔相同，则选择数值最小的那个天体 。 输入:  多行输入，每行包含一个天体标识符  和一个时间戳 ，由空格分隔。  输出:  一行输出两个整数，分别是具有最短观测间隔的天体  和具有最长观测间隔的天体 。  解题思路 这是一个模拟和最值求解问题。由于输入数据已经按照时间戳...

题目链接 古代仪式的准备 题目描述 为了启动一个古代仪式，需要在法力值上限  内，选择一组魔法媒介，使得它们提供的总魔力能源  不低于仪式的最低需求 。 任务是，在所有满足  的组合中，找到一个法力总消耗  最小的方案。如果存在多个法力消耗同为最小的方案，则选择其中  最大的一个。 输入:  一行三个整数 。 接下来  行，每行包含两个整数 ，分别代表第  种媒介提供的能源和消耗的法力。  输出:  输出满足条件的最小法力总消耗，以及在该消耗下能获得的最大魔力能源。 如果无法满足最低能源需求，则输出 0 0。  解题思路 这是一个典型的0/1背包问题的变种。我们可以将法力值看作背包的“重量”，...

题目链接 星途勘测 题目描述 给定一个由  颗恒星和  条星途（边）组成的无向图。每条星途按输入顺序被唯一编号。我们需要找出所有从启程之星  到圣地之星  的简单路径（路径上恒星与星途均不重复）。 所有找到的简单路径，根据其经过的星途编号序列，进行字典序升序排列，并赋予一个从 1 开始的唯一索引。 接下来，会有  场宇宙风暴，每场风暴会摧毁一条星途。对于每次风暴，需要报告出所有被切断的朝圣路线的索引。 输入:  第一行包含四个整数 。 接下来  行，描述  条星途。 之后一行是一个整数 ，代表风暴总次数。 最后  行，每行一个整数，代表被摧毁的星途编号。  输出:  针对  次风暴，输出  行...