题目链接 石子合并 题目描述 有  堆石子排成一行，第  堆石子的质量为 。每次操作只能选择相邻的两堆石子合并，代价等于这两堆石子的质量之和。合并后形成的新石堆质量也为两者之和，并继续与左右相邻石堆相邻。目标是找到一种合并顺序，使得将所有石子合并成一堆的总代价最小。 解题思路 这是一个典型的区间动态规划问题。我们的目标是求将所有  堆石子合并为一堆的最小代价。 1. 状态定义 我们定义  为将区间 （即从第  堆到第  堆）的石子合并成一堆的最小代价。我们的最终目标是求解 。 2. 状态转移 对于区间 ，其最后一次合并必然是将两个已经合并好的相邻子区间合并而成的。我们可以枚举这个分割点 ，其中...

HIGH93 没有上司的舞会 题目描述 公司准备举办一场晚会，共有  名员工。每名员工都有一个“气氛值”，邀请他们可以为晚会增加对应的气氛值。 规则是：如果邀请了一名员工，那么他的直接上司就不能被邀请。 已知公司的层级关系是一棵树，根节点是老板。请求出一个邀请方案，使得晚会的总气氛值最大。 解题思路 这是一个经典的树形动态规划问题，通常被称为“没有上司的舞会”。核心约束是：一个节点和它的父节点不能同时被选择。 1. 模型抽象  图结构: 公司的组织架构是一棵树。我们需要先根据输入的上下级关系建树，并找到树的根节点（没有上司的员工）。 决策: 对于每个员工（树中的节点），我们都有两种决策：邀请他...

HIGH92 最大学分 题目描述 在大学选课系统中，共有  门课程，需要从中选出恰好  门。每门课程  有  的学分和至多一门直接先修课 。 选课必须满足先修课约束，即要选修一门课程，必须先选修它的直接先修课，以及先修课的先修课，以此类推，直到根课程（没有先修课的课程）。 请求出在满足约束的条件下，选修  门课程能获得的最大总学分。 解题思路 这是一个在树形依赖结构上进行选择，以在限定数量下最大化价值的问题。这是一个经典的树形背包（或称树形DP）问题。 1. 模型抽象  图结构: 课程之间的先修关系构成了一个森林（由多棵树组成）。每门没有先修课的课程（）是其所在树的根节点。 依赖关系: “选一...

HIGH91 来硬的 题目描述 共有  枚煤炭和  单位的铁矿石。第  枚煤炭可以融化  单位的铁矿石，燃烧时间为  秒。 你拥有一项魔法，最多可以对一枚煤炭施放，将其升级。若第  枚煤炭被升级，它将可以融化  单位的矿石，而燃烧时间缩短为  秒。 熔炉同一时刻只能燃烧一枚燃料。请求出将所有  单位铁矿石全部烧炼完毕，所需要的最短总时间。 解题思路 这是一个在满足特定“价值”（融化量）要求下，最小化“成本”（燃烧时间）的问题，是典型的背包问题变种。然而，由于单个煤炭的融化量  可能非常大，直接以融化量为维度的DP数组会导致内存溢出。 正确的思路是基于数据范围进行分类讨论和剪枝。任何最优解，要么...

HIGH90 小红笔试 题目描述 小红参加一场有  道题的编程笔试，总时长为  分钟。对于第  道题，她有三种选择：  写出正确算法：耗时 ，得分 。 写出暴力算法：耗时 ，得分 。 放弃此题：耗时 ，得分 。  要求规划一个做题方案，使得在总耗时不超过  的前提下，总得分最大。并输出这个方案。 解题思路 这是一个典型的分组背包问题。我们可以将总时长  视作背包的容量，每道题的得分视作物品的价值，做题耗时视作物品的重量。 1. 模型抽象  背包容量：总时长 。 物品组：共  个组，每道题构成一个独立的组。 组内物品：对于第  道题（第  组），组内有三个互斥的“物品”可供选择，分别对应三种策略...

HIGH89 【模板】分组背包 题目描述 给定  件物品与一只最大可承重为  的背包。所有物品被划分为若干个组，同一组中的物品是互斥的：对于每个组，你最多只能选择其中的一件物品。 第  件物品的重量是 ，价值是 ，所属组别为 。 请你在不超过背包承重  的前提下，选择若干物品使得总价值最大。 解题思路 这是一个经典的分组背包问题。它的特点是物品被分成了若干组，每组内的物品相互冲突，最多只能选择一个。 分组背包可以看作是0-1背包的一种扩展。在0-1背包中，我们对每个物品做决策：选或不选。在分组背包中，我们的决策单位变成了“组”：对于每一组，我们的决策是：  不选择该组中的任何物品。 选择该组中...

HIGH88 【模板】二维费用背包 题目描述 小红有  个事件可以分享。她希望在总耗时不超过 ，总消耗精力不超过  的前提下，选择若干事件进行分享，使得收获的快乐值总和最大。 对于第  个事件，若要发布，需要耗费  分钟时间与  点精力，并能让她获得  点快乐值。每个事件最多只能选择一次。 解题思路 这是一个经典的二维费用背包问题。它本质上是一个0-1背包问题，但每个物品有两个不同的“费用”（或“体积”），这里分别是时间和精力。我们需要在这两个限制条件下，最大化总“价值”（快乐值）。 1. 状态定义 由于有两个费用维度，我们的动态规划状态也需要是二维的。 我们定义一个二维数组 ， 的含义是：在...

HIGH87 【模板】多重背包 题目描述 有  种物品和一个容量为  的背包。第  种物品的体积是 ，价值是 ，并且数量最多有  件。 求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。 解题思路 这是一个经典的多重背包问题。它介于0-1背包（每种物品只有1件）和完全背包（每种物品有无限件）之间。 最朴素的想法是将第  种物品看作  件独立的、体积为 、价值为  的物品，然后直接套用0-1背包的解法。但这种方法在  很大时，总物品数量会急剧增加，导致超时。 更高效的策略是二进制优化（也称二进制拆分），其核心思想是将多重背包问题转化为一个等价的0-1背包问题，同时控制转化...

题目链接 【模板】完全背包 题目描述 有  种物品和一个容量为  的背包。第  种物品的体积是 ，价值是 。每种物品都有无限件可用。 求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。 1. 状态定义 我们使用一个一维数组  来进行状态表示。 的含义是：当背包容量为  时，能获得的最大总价值。我们的最终目标就是求解 。 2. 状态转移方程 我们依次遍历每一种物品，并用它来更新  数组。对于第  种物品（体积为 ，价值为 ），当我们考虑如何填充容量为  的背包时，存在两种决策：  不放入物品 ：这种情况下，背包的价值就是只考虑前  种物品时的价值，即更新前的 。 放入物品...

题目链接 【入门班】第k大与第m大 题目描述 给定一个长度为  的数组 。通过以下规则构造一个新数组 ： 对于  中所有长度不小于  的连续子数组，找到该子数组的第  大元素，并将其加入 。 最终，需要输出数组  中第  大的元素。 解题思路 这是一个在隐式构造的巨大集合中查找第  大元素的问题。直接构造数组  的复杂度过高，无法接受。这类问题是二分答案的典型应用场景。 我们可以二分最终的答案，设为 。然后，我们需要一个 check(x) 函数来判定一个候选值  是否可行。对于“第  大”的查询，check(x) 函数需要回答：在数组  中，大于或等于  的元素是否至少有  个？  如果 ch...

题目链接 四值零和 题目描述 给定一个  的整数矩阵。要求从四列中各选一个数，使得这四个数的和为 0。请计算共有多少种不同的选法组合。 形式化地，给定四个长度为  的数组 ，找出满足  的四元组  的数量，其中  的范围均为 。 解题思路 一个朴素的解法是使用四重循环遍历所有可能的下标组合 ，检查它们的和是否为 0。这种方法的时间复杂度为 ，会严重超时。 为了优化算法，我们可以对原方程  进行变形，得到 。 这个形式启发我们使用折半枚举（Meet-in-the-Middle） 的思想。之前我们尝试了“排序+二分查找”（超时）和“哈希表”（内存超限）的方法。为了在时间和空间上取得平衡，我们采用第...

题目链接 整点巧克力 题目描述 有  块巧克力和  天。第  块巧克力的快乐值为 。 每天开始时，前一天的快乐值会减半（向下取整）。在当天，可以按顺序吃掉若干块巧克力（也可以不吃），增加相应的快乐值。 要求设计一个方案，将所有  块巧克力在  天内吃完，使得这  天中，每天结束时最小的快乐值最大。 输出这个最大化的最小值，以及该方案下每块巧克力是在哪一天吃的。 解题思路 这是一个典型的最大化最小值问题，我们可以使用二分答案来解决。 我们二分最终的答案，即“最小快乐值” 。对于一个给定的 ，我们需要一个 check 函数来判断：是否存在一种吃巧克力的方案，使得每天结束时的快乐值都不小于 。 ch...

题目链接 【入门班】借教室 题目描述 有  天和  份订单。第  天有  个空闲教室。 第  份订单需要从第  天到第  天，每天租借  个教室。 订单按顺序处理，如果一份订单在申请的任何一天无法得到满足（即当天剩余教室不够），则该订单失败，并停止处理后续所有订单。 求第一个失败的订单编号。如果所有订单都能满足，则输出 。 解题思路 一个直接的想法是按顺序模拟处理每份订单，对于每份订单，都更新对应区间的教室数量。这种方法的时间复杂度为 ，对于  数量级达到  的数据会超时。 注意到问题要求的是第一个无法满足的订单，这具有一种临界点的特性，并且满足单调性：如果前  份订单可以被满足，那么任何少于...

题目链接 山峰数组计数 题目描述 给定一个长度为  的正整数数组 。你需要选择两个下标 （），并将  划分成三个非空连续子数组：，，。 若这三个子数组的和满足  且 ，则称二元组  可行。请计算共有多少个不同的可行二元组。 解题思路 这是一个计数问题。一个朴素的想法是遍历所有可能的  对，然后计算三个子数组的和并进行比较。这会导致  的时间复杂度，对于本题的数据范围来说太慢。 为了优化，我们可以使用前缀和来快速计算子数组的和。设  为数组  前  个元素的和（）。那么：      “山峰”条件可以转化为关于前缀和的不等式：     现在，问题转化为寻找满足  且同时满足上述两个不等式的整数对 ...