企业官网建设流程全解析

第一次看到这道 P8803 的费用报销时，我承认我被标题里的“有序集合 小根堆”晃了一下，以为又得写什么带优先队列的贪心神题。真把题面读完才发现，这道蓝桥杯 2022 国赛 B 组题一点也不神秘：它本质上是一个“带日期限制的背包问题”，核心难点不在堆，而在怎么把“日期相差不小于 K 天”这个约束干净地塞进 DP 里。本文就从读题开始，把日期离散化、同一天多张票据、K 天边界这些容易踩坑的地方全部拆开讲，最后给一份可以直接参考的 C++ 实现。

1. 读题先读限制：这不是贪心题，是“日期版背包”

1.1 报销问题的三个关键点

这题给我的第一印象是模拟，第二印象是枚举子集，读完数据范围才确认是 DP。题目大概长这样：

• 有 n 张票据，每张票据有一个“月/日”日期和一个金额；
• 任意两张被报销的票据，日期差至少要有 K 天；
• 报销总金额不能超过预算 M；
• 求能报销的最大总金额。

我建议大家把“任意两张”翻译成“选出来的票据按日期排序后，相邻两张的日期差至少 K 天”。因为日期是自然有序的，如果相邻两张都满足差 K 天以上，那么跨更多张的日期差只会更大，不会更小。

这就是一个典型的“在合法日期序列中做 0/1 选择”的模型。如果把日期约束去掉，答案就是看所有票据金额加起来能不能塞进 M；但加上日期差限制后，很多组合不能被同时选择，选这个还是选那个就需要决策了。

1.2 为什么排序加贪心会挂

有人看到“总金额不超过 M 尽可能大”，第一反应是按金额从大到小排，能选就选。这种贪心很容易挂。举个最简单的例子：

• 预算 M = 4，K = 1；
• 票据 A：日期 1，金额 3；
• 票据 B：日期 2，金额 2；
• 票据 C：日期 3，金额 2。

按金额从大到小，会先选 A，金额 3，剩下预算 1，选不了任何票据，结果就是 3。但正确的选择是 B 和 C，日期 2 和日期 3 相差 1 天，满足 K=1，总金额 4，刚好填满预算。

所以这个题的核心难点是“预算”和“日期约束”同时存在。你既要考虑金额能不能放进背包，又不能让两个日期离得太近。这种耦合关系用贪心处理非常不靠谱，老老实实上 DP 才是正路。

2. 日期离散化：把“月/日”压成一个绝对天数

2.1 月日转绝对天数的两个细节

DP 里需要比较日期差，总不能每个月日都做一次跨月计算。第一步是把“第几个月第几天”转成“从 1 月 1 日开始的第几天”。

这里有两个细节要提醒：

1. 本题只看月日，不跨年，所以直接用平年的每月天数做前缀和就行；
2. 注意前缀和的写法，别把 12 月 31 日算成 366 之类的错误值。

C++ 里可以这样预处理：

const int monthDays[13] = {0,31,28,31,30,31,30,31,31,30,31,30,31}; int prefix[13] = {0}; for (int i = 1; i <= 12; ++i) { prefix[i] = prefix[i - 1] + monthDays[i - 1]; } // 例：把 3 月 5 日转成绝对天数 int absDay = prefix[3] + 5;

这样转出来的结果里，1 月 1 日是 1，12 月 31 日是 365，日期差的比较就变成整数减法了。

2.2 同一日期出现多张票据怎么办

这是很多人第一次写错的地方。

题目规定任意两张被报销票据的日期差至少 K 天，而 K 至少是 1。那么同一天的两个票据日期差是 0，显然不满足“至少 K 天”，同一天最多只能报销一张。

所以同一日期下有多张票据时，不是一个简单的“取最大值”，因为金额大的那张可能超过剩余预算，而金额小的那张反而有用。正确做法是把同一天的每张票据都当成一个独立选择机会，让 DP 自己决定选哪张，甚至一张都不选。

这也是我后面选择按天建 DP 的原因之一：同一天的票据即便是一批，它们的转移来源也必须是“这一天之前”的状态，不能从同一天的其它票据状态转移过去。

3. 按天转移的 DP：第二维为什么必须是预算

3.1 状态定义和递推式

我们把所有票据按照绝对天数放进按天分组的结构里，然后定义：

f[d][j]：只考虑日期从第 1 天到第 d 天的票据，在总金额不超过 j 的前提下，能拿到的最大金额。

这里的状态含义是“不超过 j”，而不是“恰好等于 j”，这是为了让状态能天然继承剩余预算。初始化时全部为 0，因为什么都不选也是合法方案。

转移分两种：

1. 第 d 天不选任何票据，直接把前一天的状态继承下来：f[d][j] = f[d-1][j]

2. 第 d 天选一张金额为 w 的票据，那么之前能选的票据日期必须不超过d - K：f[d][j] = max(f[d][j], f[max(0, d-K)][j-w] + w)

为什么来源是max(0, d-K)？因为“日期差至少 K 天”翻译成不等式就是：如果这次选的票据日期是 d，那么之前选的那张票据日期 p 必须满足d - p >= K，也就是p <= d - K。所有日期小于等于d-K的合法方案，都已经汇总在f[d-K]这个状态里了。

3.2 一个特别容易写错的边界

很多初学者会把转移来源写成d - K - 1或者d - K + 1，这两种都会错。

• 写成d-K-1，会把“恰好相差 K 天”的合法组合漏掉；
• 写成d-K+1，会把只差K-1天的非法组合算进去。

举个例子，K=2 时，第 5 天的票据和第 3 天的票据日期差是 2，合法，所以第 5 天转移时应该能用到f[3]的状态，也就是d-K。如果写成d-K-1=2，就漏了 3 号这一批。

3.3 为什么这样转移不会漏解

用归纳的思路看：对于任意一个最优解，只看它里面日期最大的一张票据，有两种情况。

一种是最优解里根本没有第 d 天的票据，那它本来就被f[d-1][j]覆盖到了。

另一种是最优解在第 d 天选了一张金额为 w 的票据。去掉这张票据后，剩下的票据日期都必须满足“与第 d 天相差至少 K 天”，也就是日期不能超过d-K，这些票据组合出来的总金额一定不超过j-w。而f[d-K][j-w]已经记录了这类组合里的最大值，所以加上 w 一定能覆盖这个最优解。

这两个情况都覆盖到，递推就是完备的。

4. 完整实现：map 收集日期，数组保存状态

4.1 可以直接参考的 C++ 代码

我用map<int, vector<int>>按日期分组，map的键本身就是有序的，正好对应标题里的“有序集合”。DP 状态用vector<vector<int>>存，天数最多 365，M 最大取 5000，内存完全够用。

#include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, M, K; cin >> n >> M >> K; int monthDays[13] = {0,31,28,31,30,31,30,31,31,30,31,30,31}; int prefix[13] = {0}; for (int i = 1; i <= 12; ++i) { prefix[i] = prefix[i - 1] + monthDays[i - 1]; } map<int, vector<int>> bills; for (int i = 0; i < n; ++i) { int m, d, w; cin >> m >> d >> w; if (w > M) continue; // 单张就超预算，后面不可能选它 int absDay = prefix[m] + d; bills[absDay].push_back(w); } vector<vector<int>> dp(366, vector<int>(M + 1, 0)); for (int day = 1; day <= 365; ++day) { dp[day] = dp[day - 1]; if (!bills.count(day)) continue; int source = max(0, day - K); for (int w : bills[day]) { for (int j = M; j >= w; --j) { dp[day][j] = max(dp[day][j], dp[source][j - w] + w); } } } cout << dp[365][M] << '\n'; return 0; }

这段代码里要注意一个细节：处理某一天的多张票据时，转移来源始终是dp[source]，而不是dp[day]。因为source一定小于day，所以同一张票据不会和同一天的其它票据组合，正好满足“同一天最多选一张”的限制。

4.2 复杂度分析

• 预处理日期：O(N)
• 按天复制状态：O(365 × M)
• 每张票据的金额转移：O(N × M)

总复杂度差不多是O((365 + N) × M)。即使 N 取 1000、M 取 5000，也就几百万次运算，在这个数据范围下完全够用。

空间上dp是366 × (M+1)个int，大约 7MB 多一点，蓝桥杯考场环境完全不用担心。

5. 边界用例、常见坑和自测方法

5.1 K 比最大日期还大

如果 K 是 365 甚至更大，那么任意两张票据的日期差都不可能达到 K 天，答案就是“最多只选一张，且金额不能超过 M”。

在这个 DP 里，day-K会变成负数，我用max(0, day-K)把它强制拉回 0。这样每张票据都只能从空状态转移，天然只会选一张，不需要特判。

我自己第一次写的时候忘了max(0, ...)，数组下标直接越界，运行就崩了。所以这个max(0, ...)不是可选项，是必须写的。

5.2 同一天多张票据的“陷阱”

假设某一天有三张票据，金额分别是 2、5、8，K=2，预算 M=10。

按照正确规则，这一天最多只能报销一张，所以可选的方案是取 2、取 5、取 8，或者一张不取。我的代码里三个金额都会被放进同一天的vector<int>，然后分别从source状态尝试转移；因为它们都只用dp[source]，不会出现“先取 2 再取 5”这种同一天组合。

如果你把转移来源写成dp[day][j-w]，那就会在同一天内部不断叠加，等于让同一天的多张票据可以同时报销，结果就会错得很离谱。

5.3 一个顺手自测的小样例

可以拿这组数据试试：

3 4 1 1 1 3 1 2 2 1 3 2

期望输出是 4。因为第 2 天和第 3 天的两张金额为 2 的票据可以一起报，日期差是 1，刚好满足 K=1，总金额 4 不超过预算。如果程序输出 3，说明贪心思想还没清干净，或者是 DP 的第二维“不超过 j”处理有问题。

再试一个同一天的用例：

2 10 1 1 1 6 1 1 5

正确结果是 6，因为同一天最多选一张，选大的那张更优。这个用例可以很快测出同一天分组是否写对。

6. 再聊聊“有序集合”和“小根堆”这两个标签

6.1 有序集合在这里到底起什么作用

本题确实用到了某种“有序日期结构”，我用的是map<int, vector<int>>。map的遍历天然按日期从小到大，这和 DP 按天推进的顺序完全吻合。

如果日期不是限定在一年内、而是一个很大的数字范围，直接用数组开不下，那也可以用set<int>只存出现过的日期，再用二分查找找“小于等于 day-K 的最大日期”。但本题日期最多 365 天，直接按天滚动反而是最简单、最不容易出错的做法。

所以“有序集合”不是神兵利器，它只是在日期比较分散时的一种组织方式。真正的核心仍然是 DP 的状态设计。

6.2 小根堆为什么不建议优先去想

有些类似的报销题、选区间题，确实能用“反悔贪心 + 最小堆”来解：维护当前已经选的若干项，如果超过预算就从堆顶弹掉最小的一项。这类题通常只需要求“最多能选多少项”，或者没有日期差这种强前缀约束。

而这道费用报销的问题是“总金额不超过 M 的前提下求最大金额”，它同时受到预算上限和日期差两个条件的约束。贪心堆很难同时处理这两个维度，一个简单的贪心反例就能把它打回原形。

我个人的经验是：看到题目里同时出现“金额上限”和“选择限制”两个词，第一优先考虑的永远是背包 DP，而不是贪心堆。标签可以当作思路参考，但不能一上来就硬套堆。

现在再回头看这道题，我会把它的标签读成“用有序日期组织状态，用数组做背包”，而不是“需要小根堆”。先搞清状态维度，再想优化，比记住某个数据结构要重要得多。