【UR #26】 铁轨回收
一道玩状态设计的超厉害题目。
首先有一个经典的 dp。从前到后做记录被加了 \(j\) 的数有 \(c_j\) 个。可以过 \(B_n \le 4\)。
想要扩展一下这个做法，直接记 \(S\) 表示后面加数的集合。很显然会直接爆炸。
但是呢，有一个很美妙的性质，就是一个位置上加的数是有上界的，但是如果我们从前往后 dp 势必无法利用这一上界。因此考虑从后往前 dp。反过来想，如果我们希望控制状态数，那么一个思路是考虑 \(A_i\) 有没有顶到 \(B_i\) 的上界，如果整个过程中都没有顶到上界，那么就相当于一切数最终都到了 \(A_n\) 这，状态数就是 \(O(\pi (B_n))\) 的。这样，考虑容斥，将顶到上界的情况转化成所有情况减去没有顶到上界的情况。所以我们只需在 dp 过程中多记录一维表示多少点是我们钦定计算所有情况的。
具体转移就很简单了，需要特别注意加 \(0\) 的情况，不要算重了。
代码写了 7 个小时，有点细节的。