自从我学了编程, 我的生活就像打开了一扇新的大门, 充满了无尽的神秘和无限的乐趣, 记的是星期天, 我参加了一场有趣的编程比赛. 星期六晚上, 我躺在床上, 心里想着今天刚学的算法. 忽然, 我身边响起很嘈杂的声音. 原来比赛已经开始了, 可我却不知道这是什么比赛. 我的周围都是各种厉害的编程大神, 他们个个信誓旦旦, 但我却忐忑不安, 心凉了半截. 开始比赛, 每个人的手指都在键盘上飞...

对于物品大小最大为 $V$ 的 Subset Sum 问题可以做到 $\mathrm{O}(nV)$ 的时间复杂度, 而传统背包 DP 解法只能做到 $\mathrm{O}(n^2V)$.

SG 定理的理论基础, 反常游戏在竞赛中的应用.

原版放送 (含标签)