🎮 游乐园峰谷过山车 II：当数据量膨胀到万亿级

“来了。”

我靠窗坐着，魔法书摊在膝上，手边一杯茶冒着热气。窗外传来熟悉的脚步声——不是那种出大事的急匆匆跑法，而是不紧不慢、带着“ 我要来吓唬你了但我其实很期待看你反应 ” 的节奏。上次游乐园试运营、正式服连着来的时候，也是这个步调。如果把村长的每次出场录下来做傅里叶变换，峰值频率大概在“焦虑”和“幸灾乐祸”之间。

门被一脚踹开。“小白！游乐园又来任务了！”他手里挥着一封烫金信封，脸上的表情比上次更兴奋。

我接过信封，没急着拆。“村长，让我猜猜——波动值 II，规则一个字没改，数据量加了一串零。对吗？”

村长愣了一下，显然没料到我预判了他的预判。我把信封拆开，果然：

3753 - 范围内总波动值 II 规则：同 3751 数据范围：1 ≤ num1 ≤ num2 ≤ 10¹⁵

10¹⁵，十五位数。上次 3751 是 10⁵，六位数，暴力法直接遍历，几十万次操作，眨眼就跑完了。这次如果用同样的暴力对付 10¹⁵，遍历次数得用“万亿”做单位——从几十万到万亿，差了整整十个数量级。上次几十万次耗时不到 0.1 秒，这次暴力能跑到地老天荒。

但我没有慌，甚至有点小得意。因为昨天的我在老勇者敲烟斗的节奏里，已经把数位 DP 的核心思想刻入脑海了。不光学会了“怎么搜”，还搞懂了“怎么记”——限制状态和计算状态分家，波动值从行李升级成战报。而那两个版本的代码，昨天就躺进我的魔法书里了，一字一句，墨迹都还没褪色。

“村长，”我把茶杯放下，翻开魔法书到那两页代码，“你看，昨天老勇者教了我两种数位 DP 写法。第一种‘行李版’，把 waviness 放在参数里一路扛下去——最符合直觉，填完所有位直接返回累加好的成绩单。第二种‘战报版’，把 waviness 踢出参数表，变成返回值的一部分，每个子树统一上报 (子树波动值总和, 子树合法数字个数)。”

我用手指点了点代码里的核心差异，继续解释：“说句公道话，今天这数据量，两种其实都能跑。10¹⁵ 是十五位数，状态总数也就几万个，行李版的缓存虽然会漏掉一些命中，但状态空间本身不大，硬跑也能过——顶多比战报版多喘两口气，不至于升天。”

“但你猜我选哪个？”我把魔法书往他面前推了推，指着第二种写法旁边昨天重重划下的那行下划线——波动值是战报，不是行李。“行李版今天能过，但如果数据量换到 10¹⁸ 呢？换到 10¹⁰⁰ 呢？行李扛一路，缓存命中率随数据量一路下滑；战报往上交，数据涨到天上去也没关系。既然昨天已经想明白了，今天就没必要退回去走老路。”

我把战报版代码原封不动贴进提交框，一个字符都没改，点了提交。绿色大勾弹出来的时候，村长正在喝我给他倒的茶。他看了看屏幕上的 Accepted，又看了看耗时——表情从“我要看你翻车”变成了“你怎么又不翻车”，嘴唇抖了三抖，最后只憋出一句：“就这？”

“就这。”我把魔法书翻到昨天写的那条批注——“波动值是战报，不是行李”——在下面补了一行新记录：

3753 - 范围内总波动值 II 解法：同 3751 数位 DP 战报版，O(位数 × 状态数)，代码零改动 数据范围：num2 ≤ 10¹⁵，位数从 6 涨到 16，状态数几乎没变 心得体会：行李版今天也能过，但既然学会了看战报，就没必要再扛行李。好的状态设计，不惧数据膨胀——昨天多想十分钟，今天省下十个数量级，连代码都不用改一行。

村长看了看我魔法书上的批注，默默喝完了杯里的茶。他站起来走到门口，顿了顿，没回头：“下次要是再来个 III，范围扩到 10¹⁰⁰——你还这么稳？”

“理论上，”我重新拿起拨火棍，往锅炉里又添了根柴，“位数再涨十倍，状态数也就多个零。只要问题本质没变，战报永远管用。”

村长哼了一声，推开门的瞬间，风把他半句话吹了进来：“……你小子，学了点东西。”

门关上。我靠在椅背上，火苗在锅炉里欢快地蹿着。魔法书摊在膝上，两行批注一上一下——3751 教会我怎么写数位 DP，3753 教会我一个更重要的道理——最好的代码不是跑得最快的，而是数据量涨一百亿倍也不用改一行的。

本作品采用 知识共享署名-非商业性使用-禁止演绎 4.0 国际许可协议 进行许可。