CF1943
flower1
·
·
个人记录
CF1943
D
Solution
考虑一个什么样的序列合法，通过观察得到结论：
定义第 i 位合法为 b_i \le b_{i-1}+b_{i+1}，一个序列合法，当且仅当其所有位合法。
必要性是显然的，b_i 最多会被减 b_{i-1}+b_{i+1}，然后 b_{i-1}，b_{i+1} 就都变为 0，此时无解。
证明必要性，对于一组符合结论的序列，我们找到第一个 b_i > b_{i+1}，再将 [1,i-1] 的 b_i 全部减成 0，这样得到的序列依然符合结论。
这样我们容易设计出 dp。设 f_{i,j,k} 为考虑前 i 位，b_i = j, b_{i-1}= k 的合法方案数，使用前缀和优化即可。
注意，f_i 的合法指的是 [1,i-1] 位合法，最后得到的答案为 \sum f_{n+1,0,x}。
时间复杂度 O(n^3)，可以通过 D1。
尝试优化，由于状态数已经是 O(n^3)，我们必须精简状态。
设 f_{i,j} 为考虑前 i 位，b_i= j 的合法方案数，转移时枚举第 i 位和第 i-2 位，这样使 i-1 位合法的方案数就是固定的。
但是这样转移会有个大问题，我们能确保 $i-1$ 位合法，但 $i-2$ 位可能不合法，因此这样转移不可行。
正难则反，考虑容斥，用前 $i-1$ 位合法的方案数减去前 $i-2$ 位合法，第 $i-1$ 位不合法的方案数。
因为有如下性质：若第 $i$ 位不合法，则第 $i-1$ 位一定合法。
证明：$b_i > b_{i-1}+b_{i+1},b_{i-1} > b_i+b_{i-2} \rightarrow b_{i+1}+b_{i-2} < 0$，矛盾。
因此如果反着转移，就可以解决刚才的问题。
$f_{i,j} = \sum\limits_{x=0}^k f_{i-1,x}-\sum\limits_{x=0}^{k-j-1} f_{i-2,x} \times (k-j-x)
使用前缀和优化，时间复杂度 O(n^2)。