铁轨

4s 512MB 伏特再次找到了工程师，请他们设计铁轨。工程师很快给出了一张模板图纸作为候选方案。 图纸上 $n$ 段铁轨排成一行，依次编号为 $1, \dots, n$。根据工程师们的设计，第 $i$ 段铁轨的尾部只能和第 $i+1$ 段铁轨的头部相连 $(1\leq i < n)$，否则铁轨会变 ......

【UR #26】 铁轨回收 一道玩状态设计的超厉害题目。 首先有一个经典的 dp。从前到后做记录被加了 \(j\) 的数有 \(c_j\) 个。可以过 \(B_n \le 4\)。 想要扩展一下这个做法，直接记 \(S\) 表示后面加数的集合。很显然会直接爆炸。 但是呢，有一个很美妙的性质，就是一个 ......

题面传送门 拜谢 zaky！ 首先考虑 \(B_i\leq 1\) 的部分分，我们考虑采用一种“提前”的 dp 方法。我们设 \(f_{i,j}\) 表示从后往前考虑到第 \(i\) 个，仍有 \(j\) 个 \(0\) 需要变成 \(1\) 的方案数。每次转移的时候枚举当前这个值最终是什么，并选择 ......