1. 从一道国赛真题说起费用报销与动态规划的实战碰撞最近在整理蓝桥杯的历年真题特别是国赛B组的题目发现“费用报销”这道题出现的频率不低而且它几乎成了检验选手动态规划DP基本功的“试金石”。题目本身描述并不复杂给你一堆带有日期和金额的发票要求在满足“日期间隔不小于K天”和“总金额不超过M”两个核心约束下选出若干张发票使得报销的总金额最大。听起来是不是有点像经典的“0-1背包问题”没错它的内核确实是背包但外壳却包裹着日期处理这个“麻烦事”。很多同学一看到“日期”、“间隔”就头大直接卡在了数据预处理上更别提后面用线性DP或者状态DP去求解了。今天我就结合自己带学生备赛和刷题的经验把这道题从里到外、从思路到代码彻底拆解清楚。我们不止要做出这道题更要弄明白为什么这道题能同时用线性DP和状态DP来解以及在实际编码中这两种思路各自的优劣和那些容易踩进去的“坑”。2. 问题本质剖析它到底是个什么问题在动手写任何代码之前我们必须先像侦探一样把题目的“伪装”剥开看清它的本质。题目给了N张发票每张发票有它的发生日期一个具体的年月日和金额一个整数值。我们的目标是挑选一个发票的子集。这个子集必须满足两个硬性条件日期约束子集中任意两张发票的日期之差按天数计算必须至少为K天。这意味着你选的发票不能太密集。金额约束子集中所有发票的金额总和不能超过给定的上限M。在这个前提下我们要最大化这个子集的金额总和。输出这个最大的可报销金额。2.1 核心模型识别带额外约束的0-1背包首先忽略日期只看金额和总上限M。这就是一个标准的0-1背包问题每张发票物品有重量金额和价值金额这里价值等于重量背包容量是M我们要在不超过容量的前提下最大化总价值。这是动态规划的经典场景。但是日期约束打破了物品之间的独立性。在标准背包里物品选不选只和容量有关和其他物品无关。而在这里是否选择第i张发票会影响到所有日期与它相隔不足K天的发票的选择可能性。这引入了物品间的“互斥”关系。2.2 日期约束的转化排序与状态定义的关键如何处理这种基于日期的互斥关系一个非常自然的想法是按日期对所有发票进行排序。一旦排好序日期约束就从一个复杂的二维关系任意两张之间简化成了一个一维的、相邻相关的约束对于排序后的第i张发票我们只需要关心在它之前最后一张被选中的发票是谁并且确保它们的日期差≥K。这引出了动态规划状态定义的一个关键点我们需要在状态中记录“最后一张被选中的发票的日期”或者其索引。因为只有知道了最后一张选的是谁才能判断当前这张能不能选。这就是为什么这道题既能用“线性DP”一种更贴近问题原始序列的思路也能用“状态DP”本质是背包DP的变种来解决的根源。两种方法其实都在试图刻画这个“最后选择”的信息只是组织状态和转移的方式不同。2.3 输入处理日期转换是第一个拦路虎题目给出的日期是“yyyy-mm-dd”格式的字符串。在算法竞赛中处理这种日期最稳妥、最高效的方法就是将其转换为一个整数代表从某个固定起点比如公元1年1月1日或者题目可能隐含的起始年开始的天数。我们称之为“儒略日”或“日期戳”。一个常见的转换函数是int days[13] {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}; bool isLeap(int y) { return (y % 4 0 y % 100 ! 0) || (y % 400 0); } int convert(int y, int m, int d) { int total 0; // 计算年份贡献 for (int i 1; i y; i) total 365 isLeap(i); // 计算月份贡献 for (int i 1; i m; i) { total days[i]; if (i 2 isLeap(y)) total 1; } // 加上天数 total d; return total; }将每张发票的日期字符串解析为年、月、日三个整数然后调用convert函数得到整数日期戳date_i。将所有发票按date_i从小到大排序。排序后日期处理就变成了对整数序列的处理简单多了。注意这里有一个非常重要的细节排序时一定要把日期和金额绑定在一起作为一个结构体进行排序。不能单独对日期数组排序否则金额和日期的对应关系就乱掉了。通常我们定义struct Invoice {int date; int value;} invoices[N];然后按date排序。3. 解法一线性动态规划思路详解“线性DP”这个说法在这里可能有点泛我更喜欢称之为“基于序列末尾状态的DP”。它的核心思想是定义dp[i]为考虑前i张发票并且“必须选择第i张发票”时能获得的最大报销金额。注意这个“必须选择”的限定。它强制让状态dp[i]与第i张发票绑定这样我们就天然地知道了“最后一张选中的发票”是第i张。接下来我们要从前面找到一张能和第i张搭配的发票j。3.1 状态定义与转移方程状态定义dp[i]表示从前i张发票中选并且第i张发票被选中的情况下能得到的最大报销金额。状态初始化dp[i] value[i]。因为如果只选第i张金额就是它本身。前提是value[i] M金额不超过上限否则dp[i]可以初始化为一个无效值如-INF表示这种状态不可达。状态转移对于第i张发票我们需要找到前面的一张发票j满足两个条件date[i] - date[j] K日期间隔约束。在选择了j的基础上再选择i总金额不超过M。这个约束在转移时通过判断dp[j] value[i] M来体现。 那么dp[i]就应该在所有满足条件的j中取dp[j] value[i]的最大值。即dp[i] max(value[i], max_{j i date[i]-date[j]K} { dp[j] value[i] })注意value[i]对应的是前面找不到任何满足条件的j的情况即第i张是选中的第一张发票。3.2 高效查找合法的j二分搜索优化直接遍历所有j i来检查条件时间复杂度是O(N²)在N较大时比如10^5会超时。如何优化 注意到发票已按日期排序date数组是单调递增的。对于固定的i我们要找的是最大的那个j满足date[j] date[i] - K。因为dp数组我们维护的是前缀最大值越靠后的j其dp[j]可能越大但不绝对所以需要维护前缀最大值。我们可以用一个额外的数组preMax来辅助preMax[i]表示dp[1]到dp[i]中的最大值。对于每个i我们用二分查找lower_bound或upper_bound在date[1...i-1]中找到最后一个日期 date[i]-K的索引pos。如果pos存在pos 1那么dp[i] max(value[i], preMax[pos] value[i])。同时更新preMax[i] max(preMax[i-1], dp[i])。这样查找j的过程从O(N)降到了O(log N)整体复杂度为O(N log N)。3.3 最终答案与边界处理最终答案并不是dp[N]因为最优方案不一定以第N张发票结尾。答案是所有dp[i]中的最大值也就是preMax[N]。边界情况如果某张发票金额value[i] M它根本不可能被选中那么dp[i]应该置为无效值并且在更新preMax[i]时不应考虑它。通常我们用-1或一个很小的负数表示无效。K可能为0这意味着日期可以相同。此时二分查找找的就是date[j] date[i]即所有之前的发票。但要注意题目描述通常K1但代码要能处理K0的情况虽然逻辑上就是无日期约束的背包。二分查找时要确保搜索范围是[1, i-1]。3.4 线性DP代码框架与注释#include bits/stdc.h using namespace std; const int MAXN 1005; // 根据题目数据范围调整 const int INF 0x3f3f3f3f; struct Invoice { int date; // 转换后的整数日期 int value; // 金额 } inv[MAXN]; int dp[MAXN]; // dp[i]: 以第i张发票结尾的最大金额 int preMax[MAXN]; // preMax[i]: dp[1..i]的最大值 vectorint dateVec; // 用于二分查找的日期数组 int main() { int N, M, K; // 读入N, M, K // 读入N张发票解析日期并转换为整数日期戳存入inv[i].date, inv[i].value // 1. 按日期排序 sort(inv 1, inv 1 N, [](const Invoice a, const Invoice b) { return a.date b.date; }); // 2. 初始化 dateVec.push_back(-1); // 使下标从1开始填充一个无效值 for (int i 1; i N; i) { dateVec.push_back(inv[i].date); dp[i] -INF; // 初始化为负无穷表示不可达 preMax[i] 0; } preMax[0] 0; // 3. DP过程 for (int i 1; i N; i) { int curVal inv[i].value; int curDate inv[i].date; // 如果单张发票金额就超限则不可能以它结尾 if (curVal M) { dp[i] -INF; preMax[i] preMax[i-1]; continue; } // 二分查找最后一个日期 curDate - K 的发票索引 int targetDate curDate - K; // upper_bound 找第一个 targetDate 的位置减1得到 的位置 int pos upper_bound(dateVec.begin() 1, dateVec.begin() i, targetDate) - dateVec.begin() - 1; // 注意dateVec.begin()i 是第i个元素的位置搜索范围是[1, i-1] int bestPrev 0; // 前面找到的最佳基础金额 if (pos 1) { bestPrev preMax[pos]; } // 状态转移要么自己单独成一组要么接在某个合法的发票后面 if (bestPrev curVal M) { dp[i] max(curVal, bestPrev curVal); } else { // 即使找到pos但加上当前金额超限也只能自己单独成组如果自身不超限 dp[i] curVal; } // 更新前缀最大值 preMax[i] max(preMax[i-1], dp[i]); } // 4. 输出答案 cout preMax[N] endl; return 0; }这个框架清晰地展示了线性DP的思路。它巧妙地利用排序和二分将日期约束转化为对有序序列的快速查询。4. 解法二状态动态规划背包DP变种思路详解“状态DP”在这里指的是更经典的背包DP思路。我们定义dp[i][j]但“状态”j不再是简单的金额而是日期。这是一种“以日期为容量”的背包思想。4.1 状态定义与转移方程状态定义dp[t]表示在“最后一张选中的发票日期不超过第t天”的前提下能获得的最大报销金额。 注意这个定义和线性DP的dp[i]以第i张结尾不同。这里的t是日期值而不是发票索引。状态转移考虑所有发票。对于一张日期为d、金额为v的发票如果我们决定选择它那么在选择它之前最后一张选中的发票日期必须 d - K。因此转移方程为dp[d] max(dp[d], dp[d - K] v)。 但这只是一个粗略的想法因为d-K可能不是某个发票的精确日期而且我们要确保金额不超过M。更精确的做法是我们将日期离散化并作为DP的维度之一。但更常见且易于实现的方法是结合贪心思想对所有发票按日期排序。定义dp[i]为考虑前i张发票不一定选第i张能获得的最大金额。这是标准的“前i个物品”的背包状态。转移时对于第i张发票我们可以选择“不选”则dp[i] dp[i-1]或者选择“选”那么我们需要找到前面最后一个能和第i张共存的发票jdate[i] - date[j] K。如果选那么dp[i] max(dp[i], dp[j] value[i])前提是dp[j] value[i] M。看出来了么这个状态定义下的转移和线性DP非常相似但dp[i]的含义不同。这里的dp[i]是“考虑前i张”的最大值而线性DP的dp[i]是“以第i张结尾”的最大值。最终答案都是dp[N]。4.2 两种DP定义的对比与选择线性DP末尾状态型dp[i]以第i张结尾的最大值。优点状态定义直观强制关联了最后一张发票方便处理日期约束。最终答案需要遍历所有dp[i]取max或用preMax[N]。缺点需要维护一个前缀最大值数组preMax来辅助快速转移。状态DP前缀状态型dp[i]考虑前i张的最大值。优点更符合经典背包的思维模式最终答案直接是dp[N]。缺点在“选”第i张进行转移时同样需要找到合法的j其状态值dp[j]表示考虑前j张的最大值这个值可能包含了以某张发票结尾的方案也可能不包含逻辑上稍微绕一点。但转移方程本质上和线性DP加preMax是一样的。在实际编码中两种方法的核心都是排序 二分查找 动态规划。性能上几乎没有差别。你可以根据个人思维习惯选择。我个人的经验是教学时用“线性DP末尾状态”更容易让学生理解日期约束是如何融入状态的而自己写代码时用“状态DP前缀状态”写起来更简洁因为dp数组直接就是最终答案。4.3 状态DP的代码实现要点// 假设inv[]已按日期排序 int dp[MAXN]; // dp[i]: 考虑前i张发票能获得的最大金额 vectorint dates(1, 0); // 日期数组下标从1开始 for (int i 1; i N; i) dates.push_back(inv[i].date); dp[0] 0; for (int i 1; i N; i) { // 不选第i张 dp[i] dp[i-1]; // 尝试选第i张 int curDate inv[i].date; int curVal inv[i].value; if (curVal M) continue; // 单张超限不可能选 int targetDate curDate - K; // 找到最后一个日期 targetDate 的发票索引pos int pos upper_bound(dates.begin() 1, dates.begin() i, targetDate) - dates.begin() - 1; if (pos 0) { // pos可能为0表示前面没有发票只选当前这张 if (dp[pos] curVal M) { dp[i] max(dp[i], dp[pos] curVal); } // 如果dp[pos]curVal超限但curVal本身不超限能否只选当前这张 // 注意dp[pos]包含了考虑前pos张的所有情况包括一张都不选dp[0]0。 // 所以当pos0时dp[pos]0判断条件就是 curVal M这已经由前面的if(curValM)过滤了。 // 因此如果dp[pos]curValM说明不能接在前pos张的最佳方案后当前方案不可行。 } } cout dp[N] endl;这段代码体现了状态DP的思想。dp[pos]代表了在“考虑前pos张发票”这个子问题上的最优解它已经隐含了“最后一张选中的发票日期一定不超过dates[pos]”这个信息因此可以直接用来与第i张发票组合。5. 实战中的坑点、优化与经验总结理论思路清晰了但实际把代码写对、跑通又是另一回事。下面是我在多次实现和调试这道题中总结的几个关键点。5.1 日期转换的精度与范围起点选择日期转换函数convert的起点通常是公元1年1月1日要一致。转换后的整数可能会很大比如2022年转换后是70多万。确保使用int类型足够存储通常没问题int能表示20多亿。闰年判断isLeap函数一定要写对。(y % 4 0 y % 100 ! 0) || (y % 400 0)是标准写法。这是基础但比赛时一紧张容易写错。月份天数数组days数组最好从索引1开始表示1月到12月的天数。二月先按28天算在累加月份时再根据闰年判断是否加1。5.2 二分查找的边界陷阱这是错误的重灾区。搜索区间对于第i张发票我们只能在它之前的发票里找索引1到i-1。upper_bound(begin, end, target)中的end迭代器应该指向dates.begin() i因为begini指向的是第i个元素下标i搜索区间是[begin1, begini)即前i-1个元素。返回值处理upper_bound返回的是第一个大于target的元素的迭代器。我们想要的是最后一个小于等于target的元素的索引。所以pos returned_iterator - dates.begin() - 1。pos的含义pos是索引。pos 1表示找到了符合条件的发票pos 0表示targetDate可能比第一张发票的日期还小前面没有符合条件的发票此时“前面找到的最佳基础金额”应该是0即从当前发票开始选如果upper_bound返回的就是begin1即第一个元素就大于target那么pos计算出来是0。当K0时targetDate curDate。我们要找date[j] curDate。由于日期严格递增date[i]等于curDateupper_bound找第一个大于curDate的那就是i本身的位置。pos i - 1。这意味着可以接在前一张发票后面如果日期相同间隔为0满足K的条件。逻辑是自洽的。5.3 动态规划状态的初始化与无效值线性DP的dp[i]初始化通常初始化为-INF如-1e9表示状态不可达。然后在转移时如果curVal M至少可以初始化为curVal单独选。如果curVal M则dp[i]保持-INF并且在更新preMax[i]时不能考虑它preMax[i] max(preMax[i-1], dp[i])因为dp[i]是负无穷所以preMax[i]就等于preMax[i-1]。状态DP的dp[i]初始化dp[0]0dp[i]先继承dp[i-1]不选的情况。这样即使当前发票不能选dp[i]也至少保持了之前的最优解。5.4 金额上限M的检查时机检查金额是否超限M有两个地方单张发票检查如果某张发票金额value[i] M那么它绝对不可能被纳入任何报销方案。在两种DP中都可以在循环开始时就continue掉这张发票对于线性DP则对应dp[i]置为无效值。状态转移时检查在尝试“选择当前发票i并接在j后面”时必须判断dp[j] value[i] M。如果超了这个转移就是无效的。在状态DP中如果超了就不能更新dp[i]。5.5 一个综合性的调试案例假设输入如下N4, M10, K3 发票 2022-01-01 4 2022-01-03 5 2022-01-04 3 2022-01-10 6转换日期并排序后假设转换后日期为1, 3, 4, 10金额对应。线性DP过程i1: date1, val4。pos0。dp[1]4。preMax[1]4。i2: date3, val5。target0。pos0。dp[2]max(5, 05)5。preMax[2]max(4,5)5。i3: date4, val3。target1。二分查找date1的最后一个是索引1。pos1。bestPrevpreMax[1]4。437M。dp[3]max(3, 43)7。preMax[3]max(5,7)7。i4: date10, val6。target7。二分查找date7的最后一个。date数组[1,3,4,10]最后一个7的是索引3(date4)。pos3。bestPrevpreMax[3]7。7613M超限因此只能单独选dp[4]6。preMax[4]max(7,6)7。最终答案preMax[4]7。对应方案选第1张(4)和第3张(3)金额7。不能选第4张因为如果接在第3张后总金额13超限如果单独选第4张金额只有6不是最大。通过这个例子可以看到金额约束M在状态转移时起到了关键的筛选作用。5.6 从这道题延伸开的思考“费用报销”这道题的价值在于它把日期处理和动态规划紧密结合了起来。它教会我们复杂约束的转化将“任意两张间隔≥K天”的二维约束通过排序转化为“与最后一张的间隔≥K天”的一维约束这是降低问题复杂度的关键。状态定义的灵活性动态规划的状态定义可以多种多样。“以i结尾”和“考虑前i个”都能解决问题但思考角度和初始化、转移方程略有不同。理解其本质联系都依赖于preMax或dp[pos]很重要。二分查找的优化在有序序列上快速查找满足条件的边界是竞赛中常见的优化手段。务必熟练掌握lower_bound和upper_bound的语义和返回值处理。细节决定成败日期转换的准确性、二分查找的边界、金额约束的判断时机任何一个细节出错都会导致结果错误。在写完代码后用几个小例子包括边界情况如K0 M很小日期密集等手动模拟一遍是查错的好方法。这道题在蓝桥杯国赛中出现其代码量适中但综合考察了模拟、排序、二分、动态规划等多个知识点是一道质量很高的题目。搞懂了它你对DP的理解和应用能力会上一个台阶。