做题记录 25.10.10

· · 个人记录

QOJ #9489. 0100 Insertion

先翻转序列，变成删去 0010

令 0 为 -1，1 为 +3，则每次删去一个 -1,-2,+1,+0 的部分

显然合法的序列总和必须为 0，且不存在相邻的 1，且任意前缀和为 h 的 1 前面的最大前缀和 \ge h-1，且最后一个是 0，可证这是充要的（构造为每次取最后一个前缀和最大值对应前缀中的最小值对应 0010 删去）

令 f_{i,j,k} 表示 1\sim i，前缀和为 j，前缀和最大值为 k 的方案数

s_i$ 取 $0$ 时 $f_{i-1,j,k}\to f_{i,j-1,k} s_i$ 取 $1$，$s_{i+1}$ 取 $0$ 时 $f_{i-1,j,k}\to [j+3-1\le k]f_{i+1,j+3-1,\max(k,j+3)}

时间复杂度 O(n^3)，空间复杂度 O(n^2)

代码

参考