企业官网建设流程全解析

在 AcWing 上刷题，很多人都有过这种体验：一道题 AC 了，队友问你怎么做的，你讲着讲着突然卡住，最后只能甩一句"就是那样转移的嘛"糊弄过去。等过几周再看这道题，你会惊讶地发现，自己居然看不懂当初写的代码了——那些状态定义和边界条件仿佛失忆一样，完全想不起来当初是怎么凑出来的。我管这类题叫"需要反复品味思路的题"。它们不是那种难到让你心态爆炸的硬核题，而是代码短、模型绕、思路藏得深，第一遍 AC 只是开始，真正的收获在第二遍、第三遍品味里。这篇就聊聊我这两年陆续遇到的这类题，以及我是怎么把"看过题解"变成"真正想通"的。如果你正在刷 AcWing 的基础课、提高课，或者准备算法竞赛，这篇文章应该能给你一份具体的参考。

1. 先定义清楚：什么样的题才算"需要反复品味"

1.1 不是最难的那些，而是最"绕"的那些

AcWing 上从不缺难题：网络流、平衡树、计算几何，每一块都有让你怀疑人生的题目。但这些题大家一开始就知道它难，啃的时候有心理准备，AC 不了也不会太意外。真正容易骗过人的是另一批题——题面读起来像小学奥数，代码写出来不到三十行，但状态定义、模型转化稍微想偏一点，整道题就全歪了。比如"方格取数"，看完题你第一反应肯定是"走两次，每次单独取最大值就行"，然后交上去 WA 得莫名其妙。这种题不会让你产生"这题好难"的感叹，只会让你反复怀疑"我到底哪里理解错了"。恰恰是这种"绕"最值得反复品味，因为它的坑不在实现，在思维。

1.2 题解看得懂，不代表思路想得通

我身边很多刷题很猛的人，都经历过"对着题解点头如捣蒜，合上题解第一行就卡住"的尴尬。这不是记性差，而是大脑的流畅度错觉在做怪——读别人推导好的过程是很流畅的，大脑会误以为自己也会推导。真正想得通的标志是：你能不靠任何提示，从问题本身一步步推到那个解，并且说清楚每一步是"怎么想到的"。所以我理解的"反复品味"，不是反复去看题解，而是反复去重构思路，把自己当成那个第一次解这道题的人，重新走一遍从题目到答案的路。

1.3 这类题的三个共同特征

根据我的经验，值得反复品味的题通常有三个特征：

• 题面描述特别朴素，没有吓人的术语。像"从左上角走到右下角，取两次数"，听起来就是个模拟题。
• 直接套常见模板一定会出问题，必须先把问题转化成一个已知模型。比如"整数划分"要看成完全背包，"最优贸易"要正反建图。
• 状态初始化或边界条件里藏着细节，第一遍写必错。比如股票买卖里"空仓能否买入"、方格取数里"同一点只能计一次分"。

这三个特征凑齐，基本就是一道值得放进"反复品味清单"里的题了。下面我会挑几个具体例子展开，从 DP、图论、模型伪装、状态压缩这几个角度，讲讲我到底在品什么。

2. DP 篇：状态的命名，决定你能不能想清楚

2.1 方格取数：把"走两次"改写成"两个人并排走"

先看题面：一个 n×n 的方格图，每个格子有一个非负整数。从左上角走到右下角，每次只能向右或向下。第一次走完后，把经过格子上的数取走（取过就变 0），再走第二次，问两次总共最多能取走多少。

第一反应通常是"走两次最优，每次单独 DP 取最大和"。这个贪心为什么错？因为第一次取走的数会变成 0，如果第一次走的是全局最优，可能把第二次原本想走的路上的数提前吸干；反过来，第一次稍微绕一点路，反而能让两条路的收益总和更大。所以两次行走是强耦合的，不能拆开。

解决这个问题的突破口，是把"先后两次走"重构成"两个人同时从起点出发，各走各的，最终都到终点"。为什么要这样改？因为两条路在空间上怎么走，本质上只和"每一步的位置"有关，跟谁先走谁后走无关；只要两个人不走到同一个格子上重复计分，最后的总分就等价于两次先后行走的分。再往下想，两个人每一步的步数是一样的，设步数 k = i1 + j1 = i2 + j2，那么只要用 k 和两个人的行号 i1、i2，就能唯一确定两个坐标组合。这就是 f[k][i1][i2] 这个状态定义的来源。

转移的时候，第 k 步两个人各有两种来源（从上边来、从左边来），组合起来就是四种情况：

// f[k][i1][i2]：k = i1+j1 = i2+j2，两条路径各走到 (i1,j1)、(i2,j2) // 下面这段示意核心转移，实际提交还要处理起点边界 f[1][1][1] = 0; // 哨兵状态，方便统一转移 for (int k = 2; k <= 2 * n; k++) { for (int i1 = 1; i1 <= n; i1++) { for (int i2 = 1; i2 <= n; i2++) { int j1 = k - i1, j2 = k - i2; if (j1 < 1 || j1 > n || j2 < 1 || j2 > n) continue; int t = w[i1][j1]; // 第一人取数 if (i1 != i2) t += w[i2][j2]; // 两人不同格才加第二人的数 f[k][i1][i2] = max(max(f[k-1][i1-1][i2-1], f[k-1][i1-1][i2]), max(f[k-1][i1][i2-1], f[k-1][i1][i2])) + t; } } }

注意转移里的四个来源：上上、上左、左上、左左。我第一次写就只写了两个方向，觉得"两个人不是都往右就是都往下"，完全忘了他们可以一个向右一个向下。这个"步数对齐"的技巧后面的"传纸条"、"双路径 DP"里还会反复出现，想通这一道，后面就都不用怕了。

2.2 股票买卖 IV：状态机最怕"交易次数"算不清楚

AcWing 的股票买卖系列是状态机 DP 的经典入口，其中"股票买卖 IV"（AcWing 1057）最需要反复琢磨。题面一句话：给定 n 天的股票价格，你最多完成 k 笔交易（买入加卖出算一笔），手里最多持有一股，求最大利润。

很多人的第一版状态是 f[i][j][0/1]，0 表示空仓，1 表示持股，j 表示已经完成的交易次数。这本身没错，但坑在"买入和卖出哪个让交易次数加 1"。题目说"完成一笔交易"是买入再卖出，所以严格讲，是"卖出"这个动作让一笔交易完整。但如果转移的时候你让卖出时 j+1，初始化会乱成一团：第 0 天完成 1 笔交易是什么意思？

我最后采用的写法是"买入时 j+1，卖出时不动"——也就是说 f[i][j][1] 表示"前 i 天，已经发起了 j 次买入，当前持股"。这样初始状态是干净的：第 0 天只有 f[0][0][0] = 0 合法，其余全是负无穷。转移长这样：

for (int i = 1; i <= n; i++) { for (int j = 0; j <= k; j++) { // 今天空仓：昨天空仓，或者昨天持股今天卖出 f[i][j][0] = max(f[i-1][j][0], f[i-1][j][1] + a[i]); // 今天持股：昨天持股，或者昨天空仓今天买入 f[i][j][1] = f[i-1][j][1]; if (j > 0) f[i][j][1] = max(f[i][j][1], f[i-1][j-1][0] - a[i]); } }

这里为什么要"卖出不动、买入加一"？因为一笔交易由"买"发起，由"卖"确认。让发起动作计数，能保证任何时刻"买入次数大于等于卖出次数"，符合"先买后卖"的约束。你如果反过来做也不是不行，但空仓和持股的状态定义就要互相嵌套，写着写着容易绕进去。这种语义上的小选择，恰恰是反复品味的价值：第一遍看题解觉得"都行"，真自己初始化的时候才知道差之毫厘谬以千里。

最后答案要扫一遍 max(f[n][j][0])，因为最后一天手里必须空仓，才能保证交易是闭环的。这个细节我第一遍也没想到，只输出了 f[n][k][0]，结果少算了很多合法方案。

3. 图论篇：读题的时候，就要开始翻译模型

3.1 最优贸易：为什么要正反建两张图

"最优贸易"（AcWing 341）是很多人口中的"第一道读不懂的图论题"。题面是：一张 n 个点 m 条边的有向图，每个点有一个水晶球价格。你从 1 号点出发走到 n 号点，途中可以在某个点买入一个水晶球，在之后某个点卖出，问最多能赚多少差价。也可以选择不赚。

初看像 DP 又像最短路，直接套最短路求"路径上最小价格"显然不对，因为你必须在买入点之后才能卖。"路径上的最小值"这个信息是不带顺序的。关键转化是把问题拆成两半：先正向跑一遍，算出 dmin[i]——从 1 到 i 的任意路径上，能拿到的最小买入价；再反过来从 n 出发，在反向图上跑一遍，算出 dmax[i]——从 i 到 n 的任意路径上，能拿到的最大卖出价。只要 i 本身在一条从 1 到 n 的通路上，dmax[i] - dmin[i] 就是一个合法方案的收益上界，答案取所有 i 的最大值即可。

为什么要建反向图？因为"从 i 到 n"的信息，在正向图上没法一次遍历得到。反过来就不一样了：从 n 出发，沿着所有边的反向边走，凡是能走到的点，都属于"能到达 n"的点集，同时可以一路维护能拿到的最大价格。这就是把"到达性"转换成"可达性"的标准技巧。单独提出来说：正向图算"从起点来"，反向图算"到终点去"，凡是遇到路径前后有限制条件的问题，都可以想想这个套路。

实现上，因为边不带负权，理论上 Dijkstra 也行；但这个题的松弛本质是dmin[v] = min(dmin[v], min(dmin[u], price[v]))，不是一个普通的最短路，SPFA 写起来更顺手，也方便扩展到更一般的"带状态的转移"：

dmin[1] = price[1]; queue<int> q; q.push(1); while (q.size()) { int u = q.front(); q.pop(); for (int v : g[u]) { if (dmin[v] > min(dmin[u], price[v])) { dmin[v] = min(dmin[u], price[v]); q.push(v); } } } // 反向图同理求 dmax，从 n 出发 int ans = 0; for (int i = 1; i <= n; i++) ans = max(ans, dmax[i] - dmin[i]);

3.2 顺着这个题，你能摸到"分层图"的门

最优贸易还有个味道更重的理解方式：把每个点拆成"未买入"和"已买入"两层。在未买入层，可以沿着原图走；要买入，就从未买入层跳到已买入层对应的点，代价是 -price；在已买入层，沿原图走，最后到终点时如果还拿着水晶球，可以跳到终点的"已卖出"虚拟点，代价加 price。这样整个问题就变成一张分层图上的最短路或者最长路，所有"动作"都变成"跨层边"。这个视角我觉得比正反图更防呆，只是建图麻烦一些。

分层图思想在 AcWing 里出现频率很高，例如"通信线路"这类"可以免费 k 次边权"的题，本质也是拆出 k+1 层。把最优贸易反复品味到位，后面遇到"带状态的最短路"就会轻松很多。我的建议是两种做法都写一遍：正向/反向图练拆解，分层图练建模，互相印证之后，你对这道题的理解就很难再忘了。

4. 伪装篇：你看到的题面，未必是它真正的模型

4.1 整数划分：一道披着数论外衣的完全背包

整数划分（AcWing 900）题面极其朴素："把正整数 n 拆成若干正整数之和，求方案数"。第一眼看过去，你会想组合公式、递推、甚至母函数，就是想不到背包。但如果把"正整数"看成物品集合：每个整数 i 是一个体积为 i、数量无限的物品，n 是背包容量，那么"把一个数拆成若干数之和"就等价于"从 1,2,...,n 中任意选若干个数，刚好凑满容量 n"，这不就是完全背包求方案数吗？

于是转移极其简单：

f[0] = 1; for (int i = 1; i <= n; i++) { for (int j = i; j <= n; j++) { f[j] = (f[j] + f[j - i]) % MOD; } }

看到这里你可能会觉得"哦，原来如此"。但注意，这个模型很容易被一个细节击穿：如果题目改成"划分成的整数不能重复"，同一个写法，内层循环方向要反过来，变成for (int j = n; j >= i; j--)，也就是从完全背包退化成 01 背包。所以反复品味这道题，品的其实是"把题面翻译成背包四要素"的过程：容量是谁，物品是谁，体积是谁，数量是无限还是有上限。这个翻译习惯养成了，你就不会再被数论外壳吓住。

4.2 石子合并：贪心直觉在区间 DP 面前为何失效

石子合并（AcWing 282）：N 堆石子排成一排，每次只能合并相邻两堆，代价是两堆重量之和，求把所有石子合成一堆的最小总代价。刚接触这道题的人几乎都会先试贪心：每次合并重量最小的两堆。这个直觉来自哈夫曼树，但哈夫曼是"任意两堆可以合并"的全局最优；限制"相邻"之后，局部最小可能毁掉后续的全局最优。

为什么区间 DP 能解决？因为一次完整的合并过程，可以看成一棵二叉树——每次合并对应一个内部节点，它的代价是"这棵子树的总重量"。把问题递归地看：在区间 [l, r] 内，最后一步一定是把 [l, k] 和 [k+1, r] 这两堆（各自内部已经合并完）合并起来，代价是区间总重量 s[r] - s[l-1]。于是：

for (int len = 2; len <= n; len++) { for (int l = 1; l + len - 1 <= n; l++) { int r = l + len - 1; f[l][r] = INF; for (int k = l; k < r; k++) { f[l][r] = min(f[l][r], f[l][k] + f[k + 1][r] + s[r] - s[l - 1]); } } }

这个转移的深层含义是：你不用枚举整棵二叉树的结构，只需要确定"根的分界点"；左右子树的最优代价已经被算好存放在 DP 表里。每次看这段代码，我都会重新体会一遍"分治思想和 DP 表结合"的美妙。值得反复品味的原因还有一个：区间长度从小到大枚举的顺序，决定了状态依赖的方向，如果 len 从 1 开始或者内层 k 乱序，结果一定会错。这个顺序问题在后面的四边形不等式优化里我又遇到过一次，印象很深。

5. 状态压缩篇：学会用"集合"当状态

5.1 最短 Hamilton 路径：从 n! 到 2^n 乘 n

最短 Hamilton 路径（AcWing 91）的问题描述很短：给定 n 个点的带权无向完全图，求从 0 号点出发、每个点恰好经过一次、最终到达 n-1 号点的最短路径长度。暴力是枚举 n! 种排列，n 一大直接爆炸。

暴力慢在哪里？排列保留了"走过的顺序"，但很多前缀顺序不同、终点相同的路径，在后续扩展时是等价的。比如"1 到 2 到 3"和"2 到 1 到 3"，当前都在 3 号点，也已经经过了 {1,2,3}，再往后走时，这两个历史谁更短只取决于"当前在哪个点"和"已经走过哪些点"，至于具体顺序并不重要。所以状态可以压缩成 (mask, last) 两个信息：mask 是一个二进制数，表示哪些点已经走过；last 表示最后停在哪个点。f[mask][last] 表示"从起点出发，走完 mask 里的点，最后停在 last"的最短长度。

转移就是枚举 last 的"上一个点 prev"：

memset(f, 0x3f, sizeof f); f[1][0] = 0; // 只从 0 号点出发，集合中只有 0 号点 for (int mask = 1; mask < (1 << n); mask++) { for (int last = 0; last < n; last++) { if (!(mask >> last & 1)) continue; for (int prev = 0; prev < n; prev++) { if (!(mask >> prev & 1)) continue; f[mask][last] = min(f[mask][last], f[mask ^ (1 << last)][prev] + w[prev][last]); } } } // 答案是 f[(1<<n)-1][n-1]

这个题我第一次看到状态定义时觉得"凭什么能这样压"，后来才意识到：凡是路径类问题，只要后续决策只依赖"已访问集合加当前位置"而不依赖访问顺序，就可以用 bitmask 来压缩。它是之后几乎所有状压 DP 的原型，包括蒙德里安的梦想、小国王、玉米田这些题，本质都在用不同的方式编码"集合状态"。

5.2 不要把状压 DP 想得太玄：它只是用二进制编码集合

很多新手觉得状压 DP 是"另一个世界"，一看到位运算就发怵。我觉得问题出在把状态压缩当成了一个独立知识点，而没有意识到它其实是一件很自然的事情：当你需要在 DP 表里记录"一个集合"时，最直接的办法就是用二进制。mask 的第 i 位是 1，表示 i 号元素在集合里；mask ^ (1 << last)表示从集合里删掉 last；mask >> last & 1用来判断 last 在不在集合里。仅此而已。

什么时候该用状压？简单判断标准就是：n 的范围通常不超过 20。因为 2^n 个状态不是你随便能枚举的，n=25 的时候就 3355 万了，再乘个 n 基本跑不动。所以遇到 n 很小、状态是"集合"的题，第一个想到的就应该是状压 DP。这个"看到小 n 就想到集合状态"的反射，就是从那道最短 Hamilton 路径里反复品味出来的。

6. 反反复复品味，到底怎么操作

6.1 三刷法：一刷靠自己，二刷靠默写，三刷靠时间

第一遍：拿到题先独立想 30 分钟以上，不管想没想出来，都要记录卡在哪一步——是状态定义不出来，还是转移写不出来，还是不知道该用什么模型。这一步决定你后面的品味有没有靶心。第二遍：看题解或讨论区，关键是看完后合上，自己默写完整代码加注释，卡住的地方标记出来。第三遍：一周后再回来，不看任何资料，重新从题面出发做一遍。如果还能顺畅做出来，说明思路真的沉淀了；如果又卡在同一个地方，那就不是"忘了"，而是第一遍就没真正想通——这正是反复品味要解决的核心问题。

6.2 写"一句话思路笔记"

我自己的习惯是，每道反复品味的题在笔记里只留一句话，模板是"这道题的核心是把 XXX 转化成 YYY，关键信号是 ZZZ"。举个例子：

• 方格取数：把"走两次"改成"两个人并排走"，用 k 对齐步数，关键信号是"路径长度相等、无后效"。
• 最优贸易：把"买卖顺序"拆成"正向最小买入价"和"反向最大卖出价"，关键信号是"路径上带顺序约束的两个最值"。
• 整数划分：把"拆数"看成背包，关键信号是"若干正整数之和等于固定值"。

这一句话不仅要写出来，还要在 AC 当天和一周后各读一遍。读的时候问自己：如果换一道题，这个信号还能不能帮我认出模型？能，说明你品到的是通用的思路；不能，说明你只是记住了这道题的特例。

6.3 讲给别人听，是最后的验收

独学而无友，则孤陋而寡闻。能给别人讲清楚，才算真正掌握。不一定要开直播，在 AcWing 题解区写一篇题解，或者在讨论区回答别人的疑问，效果都很惊人。我在写题解的过程中，经常发现自己"以为懂了"的地方其实有个漏洞，比如股票买卖的初始化为什么这么设、方格取数为什么不用考虑两条路径相交后又分开的情况。因为 k 每一层都同时推进，两个人永远在同一"步"，相交之后共享格子只会影响那一步的收益，不会造成"跨步"的重复计算。把这些追问理清楚，比再刷十道新题都长进。

7. 常见问题速查：这些坑，我替你先踩过了

7.1 初始化：状态定义的反面教材

状态定义得再漂亮，初始化写错全盘皆输。股票买卖那题，f[0][j][1]必须初始化成负无穷，表示"第 0 天不可能持股"，否则转移时会从非法状态里继承出看似合法的答案。Hamilton 路径那题，f[1][0] = 0漏掉的话，整个数组全是 INF，答案是错的但你又很难察觉，因为程序不报错。遇到这种问题，我的排查习惯是先把所有状态打出来看，从第一行开始手动模拟，看是哪里引入了非法的值。

7.2 边界与方向：肉眼看不见的 Bug

DP 题的边界和转移方向是重灾区。方格取数里k从 2 枚举到2n，j1、j2越界要 continue，漏了数组越界直接访问垃圾值。石子合并里len如果从 1 开始，f[l][r]会被错误地覆盖成 0，导致后续转移全错。这类 bug 的可怕之处在于它不是运行时崩溃，而是静默地给你一个错得离谱的答案。所以我现在写 DP 之前会先花两分钟确认三件事：状态数组的初始值是什么？循环从哪里开始？转移访问的子状态是否一定已经算过？

下面整理一张我踩过的高频坑位表，方便你复制到自己的笔记里：

这个表格只是起点。我的经验是，这些坑第一次踩都躲不开，关键是踩完要回到思路层面去理解它为什么是坑。比如方格取数的特判，不只是"代码加个 if"的问题，而是"两条路径共享同一格时，收益只能结算一次"这个语义的直接体现。理解了语义，你换任何一道双路径 DP 都不会错。

最后说点题外话。我见过很多刷题很猛的人，一周能 AC 上百道，但问他一两周前做过的题，连题目模型都说不出来。刷题数量当然重要，但对于这种典型的"思路题"，我更相信慢就是快。我自己的习惯是每周固定挑两三道这种题回来重做，不追求 AC 速度，只追求能不能闭卷写出来、能不能把思路讲明白。特别是上面列的这几类——双路径 DP、状态机 DP、带顺序的图论、伪装成别的模型的背包——每次重做都能感受到自己思维方式的变化。如果你也在 AcWing 刷题，建议你也给自己建一个"反复品味清单"，把那些 AC 得心虚的题放进去，隔一周、隔一个月分别回来重做一遍。你会发现，真正拉开差距的，往往不是谁刷得多，而是谁把核心思路内化得更深。