P9493 「SFCOI-3」进行一个列的排

P9493 「SFCOI-3」进行一个列的排

性质+dp

对于题目的限制，我们可以先弱化条件，把 \(L_i\) 的限制先去掉，转化为序列中至少存在一个 \(\rm mex=(0∼i)\) 的区间。

这时候有结论：序列一定是下凸的，即对于每一个 \(i\)，满足 \(0∼i\) 都为一个连续段。

这里直接引用 irris 的证明。

有了这个性质，我们就完全可以 dp 了，设 \(f_{i,j}\) 为考虑到 \(i\)，并放在 \([j,j+i]\) 中的方案数。显然从 \(f_{i-1,j}\) 和 \(f_{i-1,j+1}\) 中转移过来。

初始条件：\(f_{0,i}=\max(i-1,n-i)\ge L_i\)

转移：\(f_{i,j}=[j+i-1\ge L_i]\ f_{i-1,j}+[j+L_i\le n]\ f_{i-1,j+1}\)

转移过程满足的先前弱化的条件。复杂度为 \(O(n^2)\)。