蓝桥杯国赛费用报销题解：动态规划与日期约束的经典应用

1. 问题引入当费用报销遇上日期与金额的双重约束在算法竞赛的众多题目中动态规划DP是检验选手逻辑建模与状态设计能力的试金石。蓝桥杯国赛的F题“费用报销”正是这样一道经典的DP应用题它模拟了一个非常贴近现实的业务场景如何在给定的一堆带有日期和金额的发票中挑选出若干张进行报销使得总金额最大化同时满足“任意两张被选中的发票日期之差必须大于等于K天”以及“总金额不超过给定的上限M”这两个核心约束。这道题之所以能成为国赛级别的题目绝不仅仅是因为它考察了基础的0/1背包模型。更关键的是它将日期处理、状态压缩将日期映射为连续整数以及带有额外限制条件的DP状态转移巧妙地融合在了一起。很多初次接触的同学可能会觉得思路清晰——不就是个带限制的背包嘛。但真正动手实现时才会在日期差的计算、状态的定义与转移的细节上频频踩坑。最终能够ACAccepted的代码其背后是对问题本质的深刻理解和对边界情况的周密处理。我自己在研究和讲解这道题时最大的感触是它完美地诠释了如何将一个看似复杂的业务规则通过预处理和合理的状态定义转化为一个清晰、高效的计算机算法模型。接下来我将彻底拆解这道题从题意理解、核心思路、关键预处理到状态转移方程的推导与实现细节最后分享几个让我调试了半天的“坑点”。无论你是正在备赛的选手还是对动态规划感兴趣的学习者相信这篇超过5000字的详解都能让你有所收获。2. 题意拆解与核心约束分析要解决任何问题第一步永远是彻底、无歧义地理解题目。我们先把题目描述根据常见赛题转化为更具体的业务语言和数学模型。2.1 问题要素定义假设我们有一年的发票每张发票包含两个关键属性日期由月份mm和日期dd组成例如4月5日。题目通常会保证日期在同一年内这大大简化了处理难度。我们可以将日期转换为从年初1月1日开始计算的天数序号这是一个非常关键的预处理步骤。金额一个整数值val代表这张发票的面额。我们拥有N张这样的发票。此外我们还有两个全局约束参数K任意两张被选中报销的发票它们对应的日期已转换为天数序号之差的绝对值必须大于等于K。这意味着我们不能报销日期太过接近的发票模拟了公司财务对费用发生时间间隔的要求。M所有被选中发票的金额总和必须不超过M。这是报销的总额度上限。我们的目标是从这N张发票中选出一个发票的子集使得子集中发票的总金额尽可能大最大化同时严格满足上述两个约束条件。2.2 约束条件的深层解读这两个约束条件共同决定了本题的解题框架日期间隔约束K这个约束是本题区别于标准0/1背包的核心。在标准背包中物品之间是独立的选择任意物品组合只受容量限制。而在这里物品发票的选择与否还受到其他已选物品“日期”属性的影响。这直接导致了我们不能简单地将“发票”作为DP的状态维度因为状态需要记忆“最后一张被选中的发票是哪一天”这个信息以便判断下一张能否被选中。金额上限约束M这是经典的背包容量限制。我们的DP状态中必须包含一个维度来表示“当前已使用的金额”或“剩余的金额”。因此一个直观的DP状态设计雏形就出现了dp[i][j]表示考虑前i张发票在总金额不超过j的情况下所能获得的最大报销金额。但是这个状态无法体现日期约束。我们需要增强这个状态。2.3 状态设计的关键思路为了处理日期约束一个非常巧妙且常见的思路是对发票按日期天数序号从小到大进行排序。排序之后发票序列就有了时间上的先后顺序。此时日期间隔约束可以重新表述为如果选择了第i张发票那么下一张可以选择的发票j必须满足day[j] - day[i] K。这个重新表述带来了一个巨大的好处它让“日期约束”变成了一个关于发票索引的“可跳转”关系。对于排序后的第i张发票我们可以预处理出一个指针pre[i]它表示在排序后的发票列表中在第i张发票之前且满足与第i张发票日期相差至少K天的、最后一张发票的索引。如果不存在这样的发票则pre[i] 0我们假设一个虚拟的第0张发票其日期为负无穷金额为0。为什么是“之前最后一张”因为DP的过程是顺序考虑发票的。当我们决定是否选择第i张发票时我们需要知道如果选了它那么上一个被选的发票“可能是谁”。为了保证日期约束上一个被选的发票的日期必须小于等于day[i] - K。而pre[i]就给出了所有满足这个条件的发票中索引最大的那个。在状态转移时如果我们选择第i张发票那么我们的状态就应该从pre[i]那个状态转移过来这样就自动保证了日期间隔。于是我们的DP状态可以定义为dp[i][j]考虑排序后的前i张发票即发票1...i在总报销金额恰好为j的情况下所能获得的最大金额实际上就是j但此定义利于转移不这个定义有问题。更准确、更标准的背包定义是dp[i][j]考虑排序后的前i张发票总报销金额不超过j的情况下所能获得的最大金额。那么状态转移方程就需要考虑第i张发票选或不选不选第i张dp[i][j] dp[i-1][j]选第i张前提是j val[i]。如果选那么上一个被选的发票必须是pre[i]之前的某一张具体是pre[i]那张或者更早的。因此状态应该从dp[pre[i]][j - val[i]]转移过来并加上val[i]。即dp[i][j] max(dp[i][j], dp[pre[i]][j - val[i]] val[i])。这里有一个关键点为什么是dp[pre[i]]而不是dp[i-1]因为pre[i]保证了如果我们选了i那么pre[i]及之前的发票与i的日期差至少为K是合法的上一个选择点。而i-1可能就是i的前一天日期差为1不满足K不能作为转移来源。至此我们已经将原问题转化为了一个基于排序和预处理pre数组的、带有“状态依赖”的0/1背包问题。其时间复杂度大致为 O(N * M)在蓝桥杯的数据范围内通常是可行的。3. 从零开始的完整实现步骤理解了核心思路后我们一步步实现代码。我将过程分为几个清晰的阶段并解释每个阶段为什么要这么做。3.1 数据输入与日期转换首先我们需要读取所有发票数据。每张发票输入格式通常是mm dd val。#include iostream #include algorithm #include vector #include cstring using namespace std; struct Invoice { int day; // 从1月1日起的天数序号 int val; // 金额 }; // 每月天数表用于日期转换 int monthDays[13] {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}; // 计算从1月1日到mm月dd日的天数 int convertToDay(int mm, int dd) { int days 0; for (int i 1; i mm; i) { days monthDays[i]; } days dd; return days; } int main() { int N, M, K; cin N M K; vectorInvoice invoices(N 1); // 下标从1开始方便处理 for (int i 1; i N; i) { int mm, dd, v; cin mm dd v; invoices[i].day convertToDay(mm, dd); invoices[i].val v; } // ... 后续步骤 }注意这里假设了年份是平年。蓝桥杯题目通常不会涉及闰年但如果你看到年份是闰年且包含2月29日需要在monthDays[2]上加1。这是一个常见的边界细节虽然本题大概率不考但养成检查的习惯很重要。3.2 发票排序与预处理pre数组接下来我们对发票按day从小到大排序。排序后发票的原始输入顺序就失去了意义我们只关心它们的时间先后。// 排序注意下标从1开始所以排序范围是 invoices.begin()1, invoices.end() sort(invoices.begin() 1, invoices.end(), [](const Invoice a, const Invoice b) { return a.day b.day; // 按日期升序 });现在最关键的一步计算pre[i]。对于排序后的第i张发票我们需要找到最大的索引j(j i)使得invoices[i].day - invoices[j].day K。 最直接的方法是对于每个i从i-1向前遍历找到第一个满足条件的j。但这样复杂度是O(N²)在N较大时可能超时。更高效的方法是使用双指针 因为数组已排序day是递增的。当i向后移动时满足day[i] - day[j] K的j的下界也是单调不减的。我们可以维护一个指针p使其始终指向对于当前i来说满足条件的最大j。vectorint pre(N 1, 0); // pre[1] 0 int p 0; // 指针指向当前i对应的pre[i]候选 for (int i 1; i N; i) { // 移动指针p直到 invoices[i].day - invoices[p1].day K // 注意p指向的是上一个满足条件的我们要检查p1是否满足 while (p 1 i invoices[i].day - invoices[p 1].day K) { p; } // 循环结束后p指向的是满足 day[i]-day[p]K 的最大索引 // 但是如果 invoices[i].day - invoices[p].day K说明一个都没有则pre[i]0 if (p 1 invoices[i].day - invoices[p].day K) { pre[i] p; } else { pre[i] 0; // 实际上p就是0显式赋值清晰 } // 更简洁的写法pre[i] p; 因为p的移动逻辑已经保证了当p0时就是无合法前驱 // 但为了逻辑绝对清晰我们采用上面的写法。 // 实际上由于p是从0开始的且while循环的条件是 p1 i所以当循环结束时 // p可能指向一个满足条件的也可能一个都没有此时p0。所以直接 pre[i] p; 即可。 pre[i] p; // 这就是最终的简洁写法 }这段双指针预处理是O(N)的非常高效。pre[i]0是一个特殊标记表示在选择第i张发票时前面没有日期间隔超过K天的发票那么它就可以作为“第一张”被选的发票。3.3 动态规划状态转移现在进入DP部分。我们定义dp[i][j]考虑前i张发票排序后总报销金额不超过j元的情况下能获得的最大金额。状态维度i从0到Nj从0到M。初始化dp[0][j] 0考虑0张发票金额为0。// DP数组空间优化可采用滚动数组这里先展示二维版本便于理解 vectorvectorint dp(N 1, vectorint(M 1, 0)); for (int i 1; i N; i) { int curVal invoices[i].val; int prevIdx pre[i]; // 选择i时前驱状态是pre[i] for (int j 0; j M; j) { // 不选第i张 dp[i][j] dp[i-1][j]; // 选第i张需要满足金额条件并且状态转移从prevIdx来 if (j curVal) { // 注意是从 dp[prevIdx][j - curVal] 转移而不是 dp[i-1][j-curVal] dp[i][j] max(dp[i][j], dp[prevIdx][j - curVal] curVal); } } }这里有一个极其重要的细节状态转移方程是dp[i][j] max(dp[i-1][j], dp[pre[i]][j - val[i]] val[i])。 为什么是dp[pre[i]]这体现了“日期约束”的精髓。dp[pre[i]][x]表示在考虑第pre[i]张发票即第i张发票之前最后一个日期相差至少K天的发票时的情况。当我们决定选择第i张发票时我们“承诺”了上一次选择发生在pre[i]或更早。因此当前的状态必须基于pre[i]时的状态进行更新这样就保证了从pre[i]到i之间我们没有选择其他发票因为如果选了日期差就不满足K了从而满足了题目约束。3.4 空间优化滚动数组上述二维DP在N和M较大时例如M1000 N1000需要约4MB内存通常可以接受。但为了更优我们可以使用滚动数组将空间复杂度降至O(M)。观察转移方程dp[i][j]只依赖于dp[i-1][j]和dp[pre[i]][j-curVal]。pre[i]可能比i-1小很多所以不能简单地从i-1滚动。但我们可以用两个一维数组或者更巧妙一点直接在一维数组上操作但需要注意遍历顺序。标准0/1背包的一维优化是j从M到curVal逆序遍历以防止物品被重复选择。但这里我们的转移来源是dp[pre[i]]而不是dp[i]自身。如果我们直接用一维数组dp[j]在计算第i个物品时dp[j-curVal]可能已经被第i个物品更新过了如果j是顺序遍历这不符合dp[pre[i]][j-curVal]的定义。因此我们不能直接套用逆序。一个稳妥的、适用于本题的滚动数组方法是我们仍然使用二维的思想但只保留两行当前行cur和上一行prev。但pre[i]可能指向更早的行我们需要一个完整的、存储了所有i的dp[i][...]历史记录吗其实由于pre[i]一定小于i我们可以用一个二维数组dp[N1][M1]或者如果我们发现内存紧张可以意识到pre[i]虽然小于i但可能只小一点。为了绝对正确在竞赛中如果N和M在几千的量级直接使用二维数组是最省心、最不容易出错的。这里为了展示优化思路我们假设使用二维数组。3.5 答案输出最终我们需要的是考虑所有N张发票总金额不超过M的最大值即dp[N][M]。cout dp[N][M] endl;至此一个完整的、逻辑清晰的解法就完成了。核心代码不含IO大约在30-40行。4. 代码实现中的关键细节与易错点即使思路正确实现时也可能因为细节问题导致WAWrong Answer或TLETime Limit Exceeded。下面我结合自己的调试经验总结几个最容易出错的点。4.1 日期转换的偏移问题这是第一个坑。convertToDay函数计算的是从1月1日到该日期的天数。例如1月1日转换后是1天而不是0天。这会影响日期差的计算。在计算day[i] - day[j] K时如果K1表示至少间隔1天。那么1月1日和1月2日相差2-11天满足1是可以同时选的。这个逻辑是自洽的。关键在于你的pre[i]查找逻辑必须和这个定义一致。使用上述双指针算法时条件是invoices[i].day - invoices[p1].day K这里用的是符合“至少间隔K天”的语义。如果你错误地计算了日期比如把1月1日算作0天那么整个间隔判断就会错位。4.2 预处理pre[i]的双指针边界双指针算法写起来需要小心边界。p的初始值为0指向一个虚拟的第0张发票日期可视为-∞。while循环的条件p 1 i确保了p1是一个有效的、小于i的索引。循环内移p的条件是invoices[i].day - invoices[p1].day K。注意是p1因为我们想测试下一个候选是否满足条件。循环结束后p指向的是满足day[i] - day[p] K的最大p。如果没有任何发票满足即连p1都不满足那么p将保持为0。最后pre[i] p。 一定要自己用一个小例子比如N5模拟这个过程确保pre数组计算正确。这是整个DP正确的基础。4.3 DP状态转移的维度与含义这是最大的思维陷阱。我们定义了dp[i][j]是“不超过j”的最大金额。这是背包问题的常见定义。在状态转移时不选i直接从dp[i-1][j]继承这很自然。选i我们需要从dp[pre[i]][j - val[i]]转移过来并加上val[i]。这里j - val[i]可能为0这是允许的表示在pre[i]阶段报销总额为0。 关键是要理解dp[pre[i]][j - val[i]]已经是在“考虑前pre[i]张发票总金额不超过j-val[i]”下的最优解。在这个最优解的基础上我们添加了第i张发票总金额变为不超过j且由于pre[i]的定义日期约束自动满足。所以dp[i][j]的新候选值就是dp[pre[i]][j - val[i]] val[i]。4.4 初始化与答案初始化dp[0][j] 0是正确的。因为考虑0张发票最大金额就是0。 最终答案dp[N][M]就是所求。不需要再遍历j从0到M找最大值因为我们的状态定义就是“不超过j”所以dp[N][M]自然是在总金额限制M下的最优解。4.5 时间复杂度与优化算法的时间复杂度主要由DP部分决定为 O(N * M)。在蓝桥杯国赛环境中N和M通常都在10^3量级O(10^6)的复杂度是完全可以接受的。空间复杂度O(N*M)也通常可以接受。如果M非常大比如10^5而N也很大可能需要考虑其他优化如基于价值的DP但本题的M报销上限一般不会设置得离谱。5. 完整AC代码参考与逐行解析将以上所有步骤整合并加上必要的注释就得到了AC代码。这里我提供一份使用二维DP的清晰版本它虽然空间占用稍大但逻辑最直白易于理解和调试。#include iostream #include algorithm #include vector #include cstring using namespace std; struct Invoice { int day; // 从1月1日开始的天数 int val; // 发票金额 }; // 每月天数平年 int monthDays[13] {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}; // 将月/日转换为一年中的第几天 int convertToDay(int mm, int dd) { int days dd; for (int m 1; m mm; m) { days monthDays[m]; } return days; } int main() { int N, M, K; cin N M K; vectorInvoice inv(N 1); // 下标1~N for (int i 1; i N; i) { int mm, dd, v; cin mm dd v; inv[i].day convertToDay(mm, dd); inv[i].val v; } // 1. 按日期排序 sort(inv.begin() 1, inv.end(), [](const Invoice a, const Invoice b) { return a.day b.day; }); // 2. 预处理pre数组pre[i]表示在i之前最后一个与i日期差K的发票索引 vectorint pre(N 1, 0); int p 0; // 双指针 for (int i 1; i N; i) { // 移动指针p使得inv[i].day - inv[p1].day K while (p 1 i inv[i].day - inv[p 1].day K) { p; } pre[i] p; // p可能就是0表示前面没有满足条件的发票 } // 3. 动态规划 dp[i][j]: 考虑前i张发票总金额不超过j的最大报销额 vectorvectorint dp(N 1, vectorint(M 1, 0)); for (int i 1; i N; i) { int curVal inv[i].val; int prev pre[i]; // 选择i时依赖的状态是prev for (int j 0; j M; j) { // 不选第i张 dp[i][j] dp[i - 1][j]; // 选第i张需要金额足够并且从prev状态转移 if (j curVal) { dp[i][j] max(dp[i][j], dp[prev][j - curVal] curVal); } } } // 4. 输出答案 cout dp[N][M] endl; return 0; }逐行解析关键部分第35-40行排序sort函数对inv[1]到inv[N]排序排序依据是day字段。排序后发票按时间顺序排列。第44-50行预处理pre这是双指针法的核心。p始终指向对于当前i来说满足条件的最大索引。while循环的条件p1 i和inv[i].day - inv[p1].day K确保了p的移动是正确且单调的。最终pre[i]p。第57-65行DP转移外层循环i遍历每张发票。内层循环j遍历所有可能的报销总额0到M。dp[i][j]首先继承不选i的情况dp[i-1][j]。然后如果当前金额j足够支付第i张发票j curVal我们尝试选择它。选择它时我们是从dp[prev][j-curVal]转移过来其中prevpre[i]。这保证了日期约束。用max函数更新最优值。第69行输出dp[N][M]即为最终答案。这份代码在蓝桥杯官方评测系统上应该可以AC。它完整地体现了“排序 - 预处理前驱 - 带依赖的背包DP”这一核心解题链条。6. 举一反三变种与扩展思考AC一道题不是终点理解其思想并能解决类似问题才是。基于“费用报销”模型我们可以思考几种变种6.1 如果发票有“有效期”或“必须在一定时间内报销”怎么办这相当于给每张发票增加了一个属性最晚报销日期lastDay。约束变为选择的发票集合中每张发票的日期必须在其有效期内并且任意两张发票的日期差仍要K。这会更复杂可能需要结合贪心或更复杂的DP状态如状态中包含当前日期。6.2 如果金额M非常大例如10^9但发票总张数N较小100怎么办此时O(N*M)的DP会超时。一个经典的优化思路是交换DP的维度和状态含义。我们可以定义dp[i][s]为考虑前i张发票恰好报销总金额为s时所需的最小“最后一张发票日期”或一个布尔状态。但需要处理日期约束。另一种思路是“基于价值的DP”但本题的日期约束使得状态转移依赖前驱直接交换维度并不容易。对于N很小的情况或许可以考虑状态压缩DP状压DP枚举所有子集2^N然后检查日期和金额约束但N20左右才可行。6.3 如果约束不是“任意两张发票日期差K”而是“相邻被选发票日期差K”呢这其实是简化了因为“任意两张”比“相邻两张”更强。如果只要求相邻那么我们的pre[i]定义可以简化为pre[i] i-1如果day[i]-day[i-1] K否则需要向前找到第一个满足的。状态转移方程可能更简单但本质上还是同一类模型。6.4 如何输出具体选择了哪些发票这是一个经典的DP路径还原问题。我们需要在状态转移时记录每个状态dp[i][j]是从哪个决策选或不选以及从哪个前驱转移过来的。可以额外开一个preChoice[i][j]数组在更新dp[i][j]时如果发现从“选i”转移过来更优就记录preChoice[i][j] {prev, j-curVal}表示从dp[prev][j-curVal]选i而来。最后从dp[N][M]状态倒推即可得到选择的发票序列。7. 调试心得与赛场策略最后分享一些从这道题中提炼出的、适用于其他DP问题的通用经验。7.1 一定要手动模拟小数据这是调试DP最有效的方法。不要依赖感觉准备纸笔用题目给的样例或者自己构造的极端小样例比如N3, K1, M10一步步模拟你的代码日期转换结果、排序后的顺序、pre数组的计算、dp表格的填充。把你的计算过程和程序输出可以添加调试打印进行对比任何不一致的地方都是bug的源头。我在这道题上就是因为一开始pre数组计算逻辑有偏差导致整个DP结果错误通过模拟一个N4的例子才快速定位。7.2 状态定义要清晰并始终如一dp[i][j]是“不超过j”还是“恰好为j”这两种定义在初始化dp[0][0]和最终答案遍历j找max还是直接取dp[N][M]上都有区别。本题适合“不超过j”因为最终答案就是dp[N][M]比较方便。如果你定义“恰好为j”那么初始化dp[0][0]0其他dp[0][j]-INF表示不可达最终答案需要遍历所有jM取dp[N][j]的最大值。两种都可以但必须想清楚并在整个推导和代码中保持一致。7.3 空间优化要谨慎一维滚动数组优化虽然节省空间但会使得状态转移的逻辑变得不那么直观尤其是当转移依赖的不是i-1而是pre[i]时更容易出错。在竞赛中如果时间允许优先使用逻辑清晰的二维DP。确保算法正确性比那一点空间优化更重要。只有在内存明确不足比如M很大时才去考虑复杂的滚动优化并且要画图理清依赖关系。7.4 理解“排序”和“预处理”的威力这道题的精髓在于通过排序将原本无序的、带有二维属性日期金额的物品转化为一个一维的序列问题并通过pre数组将“日期差约束”转化为序列上的“可跳转”关系。这是一种非常经典的技巧在解决一些涉及时间区间、距离约束的调度、选择问题时经常用到。其核心思想是通过预处理将约束条件编码到状态转移的“来源”中。费用报销这道题从理解题意到AC走完整个流程你对动态规划的状态设计、预处理技巧以及边界处理会有更深的认识。它不像一些纯模板题那样枯燥而是需要你真正动脑去建模。希望这篇详细的拆解能帮你不仅AC这道题更能掌握这一类问题的思考方法。在算法学习的路上这种透过具体题目看到通用模式的能力才是最宝贵的。