企业官网建设流程全解析

做信息学竞赛的，CSP-J 历年题里有一道绕不开的完全背包，就是 P5662 纪念品。昨天我刚把题单里的 P5627 打完热身，今天继续打卡 P5662，读完题面的时候我心里就一句话：这不就是披着买卖外衣的背包问题吗？但真正动手写的时候，有几步还是容易翻车。这篇文章把完整思路、C++ 实现和我自己踩过的坑整理出来，给正在准备 CSP-J 的同学做参考。适合的读者很明确：会数组、循环、简单 DP，但看到背包题还是“题解看得懂，自己写不对”的阶段。

1. 题目到底在说什么：先拆题再动手

1.1 原题题意还原

题目场景是 N 天、M 种纪念品，你手里一开始有 T 枚金币。每天都会给出每种纪念品的价格，你在每一天里可以买卖任意多次，唯一的限制是：当天买入的纪念品当天不能卖出，最早第二天才能卖。也就是说，同一天里你可以先卖掉手里昨天或者更早买的货，再用换到的钱买入新的货，只是不能“今天买今天卖”刷差价。

最后一天结束的时候，你手里所有纪念品都会换算成现金。目标很直白：让最终金币数尽可能多。

我第一次读这个题的时候想得很简单：这跟炒股有什么区别？涨就买，跌就卖，每天操作一下不就完了？后来发现完全不是那么回事。难点在于本金有限，而每种纪念品价格每天都在变，你要决定的是“怎么分配手里所有的钱”，而不是“买哪一个”。

1.2 贪心为什么行不通

有同学会尝试一个看起来很合理的贪心：只买明天涨价最多的纪念品，把所有钱砸进去。这个思路在单品种情况下没问题，但品种一多就不行了。原因是收益和成本是耦合的，一件商品涨得猛，可能成本也高；一件涨得少，但成本极低，同样的钱可以买更多件，总收益反而更大。

举个例子你就明白了。假设手头 10 元，商品 A 今天 1 元明天 2 元，利润 1 元，涨幅 100%；商品 B 今天 2 元明天 4 元，利润 2 元，涨幅 100%。从利润率看一样，但 10 元全买 A 能买 10 件赚 10 元；全买 B 只能买 5 件赚 10 元。再看另一个例子：A 今天 1 元明天 3 元，B 今天 2 元明天 4 元。A 的利润 2、成本 1，B 的利润 2、成本 2，A 明显更优。不同商品的成本、利润互为约束，这天然就是一个背包模型：消耗“今天的价格”作为成本，获得“明天的差价”作为价值，在总金币有限的情况下最大化收益。

1.3 为什么能按天“全部卖掉再重新买”

这个题有一个很关键的等价变换：每一天开始时，可以假设手里没有任何纪念品，全是现金；然后拿现金去买当天想持有的纪念品，第二天再全部卖掉。为什么可以这样假设？因为题目允许当天无限次交易，我可以今天一早卖掉昨天买的纪念品，然后立刻用这笔钱买今天的纪念品，这就等价于“每天重新开局”。如果某件纪念品我想连续持有两天，那也完全可以从今天早上卖掉、再原价买回的角度去理解，钱不会少。

更重要的是，交易本身不产生成本，只有价格差才产生收益。所以每一天的决策只需要考虑一次：拿现有的钱，买哪些、买多少，才能让第二天的总资产最大化。N 天的问题就被拆成了 N-1 个重复的子问题，每一天都是同样的结构，这为动态规划提供了非常舒服的切入点。

2. 动态规划建模：压缩成每天一个完全背包

2.1 状态设计：dp 数组到底代表什么

对于任意一天 day，我只需要关注第二天。设当天某纪念品价格为 cost，第二天价格为 nxt，那么如果今天买入一件并在第二天卖出，我赚到的差价就是 gain = nxt - cost。如果 gain 是负数，那买它纯亏，直接忽略；如果 gain 等于 0，买不买都不影响现金，忽略它也不会错。

这里定义 dp[j] 为：在“当前这天”的决策里，总花费不超过 j 元时，通过买入并第二天卖出能获得的最大额外收益。注意“不超过”三个字，这是理解后面代码的核心。初始 dp[j] = 0，表示我什么也不买，收益就是 0，钱原样留在手里；第二天我的总现金就是原来的钱加上这笔收益。

为什么强调“不超过”？因为背包问题里的数组下标 j 经常被理解成“恰好花费 j”，但实际决策中你完全可以只花一部分钱，剩下的留在手里。如果 dp 定义成“恰好”，最后就还得枚举所有 j 再取最大值；如果定义成“不超过”，含义更贴近真实情况。下面给出的代码两种都能做，但我个人更推荐在最后统一扫一遍最大值，思路不容易乱。

2.2 转移方程与完全背包的正序循环

对于每一种纪念品，我把它看成一件可无限取用的物品，成本 cost，价值 gain。于是得到经典完全背包转移：

dp[j] = max(dp[j], dp[j - cost] + gain)

内层循环必须从 cost 到当前总金币数“从小到大”遍历。为什么正序？这是完全背包和 01 背包唯一的区别。01 背包倒序是为了避免一件物品被重复使用，完全背包内层正序，让 dp[j - cost] 在更新 dp[j] 之前已经包含了“当前这件物品被选过若干次”的情况，从而支持每件物品买任意多件。

每处理完一种纪念品，就把手上的现金更新为：

money = money + max(dp[j])，其中 j 从 0 到 money

这个 max(dp[j]) 就是在当前价格体系下，花不超过 money 的钱能赚到的最多差价。手头原本没花掉的钱本来就在，加上这个额外收益，就是第二天开始时的总现金。

2.3 复杂度分析与数据范围判断

外层循环 N-1 天，每天枚举 M 种纪念品，每种纪念品内层循环从 cost 跑到当前 money，所以复杂度大约是 O(N * M * money)。按原题数据范围，N、M 都在 100 级别，初始金币 T 在 10 的四次方级别，最坏情况计算量约一亿次，C++ 完全能扛住。

真正需要注意的是 dp 数组大小。money 会随着每天盈利慢慢变大，如果代码里把 dp 开成固定数组，比如 10005，那么当某个变体题的数据范围变大时就会越界。稳妥起见，要么按题目保证的范围开大一个数量级，要么用 vector 动态维护。后面代码里我选了固定数组加注释，实际比赛时你要根据题目说明确认上限。

3. C++ 代码实现：可直接复制的 AC 写法

3.1 完整 AC 代码

#include <bits/stdc++.h> using namespace std; const int MAXN = 105; const int MAXM = 105; const int MAXT = 100005; int price[MAXN][MAXM]; long long dp[MAXT]; int main() { int n, m, T; scanf("%d%d%d", &n, &m, &T); for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { scanf("%d", &price[i][j]); } } long long money = T; for (int day = 1; day < n; day++) { memset(dp, 0, sizeof(dp)); for (int kind = 1; kind <= m; kind++) { int cost = price[day][kind]; int gain = price[day + 1][kind] - cost; if (gain <= 0) continue; for (long long j = cost; j <= money; j++) { dp[j] = max(dp[j], dp[j - cost] + gain); } } long long best = 0; for (long long j = 0; j <= money; j++) { best = max(best, dp[j]); } money += best; } printf("%lld\n", money); return 0; }

这段代码很短，但每一行都有讲究。比赛时能默写出来是一方面，能讲清楚为什么这么写是另一方面，后者才是真正吃透这道题。

3.2 关键循环逐段解读

最外层 for (int day = 1; day < n; day++) 只循环到第 n-1 天。最后一天不再买入，因为题目要求最后一天结束后所有纪念品换算成现金，买入已经没有意义。第二层枚举每一种纪念品，先算出今天的 cost 和明天的 gain，gain 非正就跳过。这个跳过不是优化技巧，而是逻辑上可以证明：买一个明天还跌的商品，一定不会让整体变优，留着钱才是最理性的选择。

内层完全背包从 j = cost 开始，到 j = money 结束。这里 j 用 long long，是因为 money 被定义成 long long，循环变量类型要和它匹配，否则会有类型转换警告甚至隐患。转移时 dp[j - cost] 必须已经计算过，所以正序循环顺序不能改。

很多人抄题解的时候，最后一步写成 money += dp[money]，代码也能 AC。但我建议你用我这种写法：最后从头扫一遍，找出 dp[j] 的最大值。原因我在前面说过了，dp[j] 并不天然带着“不超过”的前缀最大值语义，只有当你额外维护了 dp[j] = max(dp[j], dp[j-1]) 之后，dp[money] 才一定等于全局最大值。直接加 dp[money] 在多数随机数据下能过，但理解不到位的话，换个数据形态就可能在边界上翻车。

3.3 关于 dp 数组大小的选择

我在代码里把 MAXT 开到了 100005，实际原题数据没那么大，多开几位纯粹是求稳。因为每天的收益会累加到 money 上，money 的上限到底是多少，取决于题目给的价格范围和天数。比赛时如果题面说答案在 int 范围内，你就按范围开；如果没明说，用 long long 数组加一个“足够大”的常数，通常不会出问题。

还有一个更灵活的做法：根据当前 money 动态分配 dp。每天循环开始前，用 vector dp(money + 5, 0) 声明一个新数组，等于把 dp 的上限跟着钱数走。缺点是 vector 每次重新分配有微小开销，放在这题里完全无所谓。固定数组写起来干净，适合考场，记住上限要留足就行。

4. 新手最容易踩的坑：错误答案排查实录

4.1 常见错误速查表

我把自己第一次写这题和帮别的同学调过的错，都整理在一张表里，方便你对号入座。

其中最容易让人想不通的是第一行。我自己第一次写的时候也抄过那种“简短写法”，样例过了，交上去 WA，一度怀疑人生。后来在本地打印每一天的 dp 数组才明白：dp[10] 并不一定等于 max(dp[0..10])。比如有一件商品成本 7、利润 100，另一件成本 2、利润 1，dp[7] = 100，但 dp[8] 可能只等于 101？不对，dp[8] 最多能到 101（买一个成本 2 的商品再叠加一个成本 6 的什么？如果没有成本 6 的商品，dp[8] 就只能从 dp[6] + 1 = 1 推过来，反而比 dp[7] 的 100 小很多）。这时如果你直接拿 dp[money] 当答案，就会漏掉这个 100 的收益。所以说，最后取 max 这一扫描必不可少。

4.2 用自造数据验证每一步

与其背错因，不如学会自己验证。拿一组简单数据手推一遍，印象会深很多。

假设 n=3，m=2，初始金币 T=10。三天的价格分别是：

• 第 1 天：商品 1 价格为 1，商品 2 价格为 3
• 第 2 天：商品 1 价格为 2，商品 2 价格为 2
• 第 3 天：商品 1 价格为 3，商品 2 价格为 4

第一天：看到商品 1 明天从 1 涨到 2，利润 1；商品 2 明天从 3 跌到 2，利润是负的。于是 10 元全买商品 1，买 10 件。第二天卖出得到 20 元。

第二天：手里 20 元。商品 1 从 2 涨到 3，利润 1；商品 2 从 2 涨到 4，利润 2。这时完全背包会告诉你，最优方案是买 5 件商品 2，花 10 元，赚 10 元，手里还剩 10 元不花掉。第三天卖出这 5 件商品 2，得到 20 元，加上之前剩下的 10 元，一共 30 元。

如果哪一步程序算出的结果和手算对不上，就把那一天的 dp 数组打印出来，看看第二个商品是不是没有进背包，或者 j 的循环范围是不是漏了。

4.3 对拍：写一个暴力程序兜底

手算只能验小样例，想更放心就写一个暴力程序去对拍。暴力思路也简单：枚举当天每种纪念品买多少件，把所有组合都试一遍，取收益最大值。商品数量少、钱少的时候，这个暴力可以跑得动。

配合一个随机数据生成器，在本地跑几百分钟的循环，就能把动态规划的正解和暴力结果反复比对。我平时的对拍脚本长这样：

for i in $(seq 1 1000); do python3 gen.py > data.in ./ac < data.in > ac.out ./brute < data.in > brute.out if diff ac.out brute.out > /dev/null; then echo "test $i ok" else echo "test $i failed" break fi done

gen.py 负责生成小范围随机数据，ac 是优化后的正解，brute 是暴力枚举。一旦 diff 发现输出不一致，data.in 就是最珍贵的调试样例。说实话，学会对拍之后，我做 DP 题的信心明显不一样了，很多想不明白的边界问题，交给暴力程序一问便知。

5. 从这道题聊开去：打卡刷题与 DP 延伸

5.1 P5627 作为热身题的定位

回到我今天打卡的起点，P5627 在这套题单里属于热身位。它不需要多复杂的模型，用来练读题和写代码手感挺合适。把它放在 P5662 前面，有点像跑步前先拉伸，让脑子从日常模式切到解题模式。如果你也想复现这种打卡节奏，建议不要跳过热身题直接上难题，因为竞赛状态连续性很重要，一上来就做中档题，前二十分钟可能都在找手感。

当然，这篇的核心还是 P5662 纪念品。它比热身题高出一个档次的地方在于，你需要自己从“买卖纪念品”的故事里看出背包模型。这种识别能力没有捷径，就要靠一道题一道题积累。

5.2 纪念品问题的变体与扩展

理解了这道题之后，可以试着把它往几个方向延伸。第一个方向：如果每种纪念品每天有库存上限，完全背包就变成多重背包，转移方程里要加一层数量枚举，或者用二进制优化。第二个方向：如果买入和卖出的价格不一样，有手续费，那么 gain = 卖出价 - 买入价 - 手续费，转移仍然成立，只是要重新算收益。第三个方向：如果 N 天压缩成 K 次交易机会，那就成了经典的股票问题，DP 状态要多加一维记录已交易次数。

这些变体看上去完全不同，但本质都是“把资源分配给若干选择，最大化收益”。这也解释了为什么竞赛题喜欢给题目套各种故事背景——剥掉外壳，核心模型就那么几个，纪念品是背包，股票是状态机 DP，区间调度是排序加贪心，识别模型的能力远比背代码重要。

5.3 这类背包题在 CSP-J 中的考察角度

CSP-J 的 DP 题很少直接告诉你“这是背包”，一般都会像纪念品一样，包装成买卖、打怪、攒钱之类的场景。出题人想考察的其实是两件事：第一，你能不能从题目描述里抽象出“成本”和“价值”；第二，你知不知道完全背包的内部循环为什么正序、为什么能重复选。

题目里还有一个容易忽略的约束：当天买入的纪念品当天不能卖，所有商品到最后一天都要变现。这直接导致了“按天拆子问题、每天做一个背包”的解法。如果去掉“当天不能卖”的限制，题目反而会变得复杂，因为每天都可以无限套利，赚钱速度会和价格序列的性质有关。所以这个约束其实是在给你发信号：每天之间是独立的，放心大胆地一天一天做 DP。

我个人做完这题后的体会是，像 P5662 这种题，第一次写很可能栽在 dp 的“不超过”和“恰好”这个细节上。别急着背模板，先拿笔把每天的资金流动画一遍，真正理解 money 是怎么变成第二天的 money 的，再上机写代码就顺了。打卡刷题的价值也正在于此：每道题留下一个自己踩过坑的记录，下次再遇到相似模型，就能少走一次弯路。