先总结一些充要条件。
一个人 \(i\) 选不到自己的 \(a_i\) 的充要条件为：若为左侧，则存在左侧的一个 \(j\) 满足 \(a_k\in[j,i]\) 且 \(b_k=R\) 的 \(k\) 的个数 \(> i-j\)，右侧同理，满足其一即可。
一个方案不合法的充要条件为，若对于一个 \(b_i=R\) 的 \(i\)，\(i\) 选位置时 \([a_i,n]\) 都已被选。
发现如果我们已经确定了前 \(i-1\) 个人最终到达的位置，把被选的位置看作 \(1\)，未被选的位置看作 \(0\)，还是假设 \(b_i=R\)，此时如果 \(a_i\) 已经被选择，\(i\) 最终一定会选择 \(a_i\) 所在连续 \(1\) 段右侧的那个 \(0\) 位置。
所以每填一个最终选择的位置，我们都可以动态维护下每个 \(0\) 位置的方案数权重和贡献权重，然后考虑填哪一个 \(0\) 位置即可。
但此时的状态描述还是复杂的，考虑能不能简化状态信息。
较大的 \(n\) 限制了如果我们要设状态的话，状态中只能有位置个数和人数两个信息。那就考虑设 \(dp_{i,j}\) 表示前 \(i\) 个位置填了存在编号的 \(j\) 个人的方案数，\(f_{i,j}\) 表示此时的贡献和，则显然 \(i\ge j\)。
考虑当 \(i>j\) 时，必然存在一个位置未填写，考虑枚举最后一个空位的位置 \(k\)，我们可以以该空位为分割划分子问题，有转移方程：
\[dp_{i,j}=\sum_{k=1}^{i}dp_{i-k,i-k}\times dp_{k-1,j-i+k}\times C_{j}^{i-k}\\ f_{i,j}=\sum_{k=1}^i (dp_{i-k,i-k}\times f_{k-1,j-i+k}+dp_{k-1,j-i+k}\times f_{i-k,i-k})\times C_{j}^{i-k} \]需要注意一些边界条件，比如 \(dp_{0,0}=1\)。
当 \(i=j\) 时，我们不妨枚举最后一个人最终填的位置，由于最后一个人填的时候，左右两侧都已填满，所以最后一个人实际可以填到任意一个位置上，并且填在空位上时可以朝任意一个方向，共 \(i+1\) 种不同的决策，转移方程为：
\[dp_{i,j}=\sum_{k=1}^idp_{k-1,k-1}\times dp_{i-k,i-k}\times (i+1)\times C_{i-1}^{k-1}\\ f_{i,j}=\sum_{k=1}^if_{k-1,k-1}\times dp_{i-k,i-k}\times(i+1)\times C_{i-1}^{k-1}+f_{i-k,i-k}\times dp_{k-1,k-1}\times (i+1)\times C_{i-1}^{k-1}+(w(k-1)+w(i-k))\times dp_{i-k}\times dp_{k-1}\times C_{i-1}^{k-1}\\ w(i)=\frac{(i+1)i}{2} \]时间复杂度 \(O(n^3)\)。
基于子问题的划分，思考状态的设计与转移。子问题的划分通常可以考虑最后一个决策的选取。
标签：CF1439D,一个,sum,位置,times,充要条件,Contests,INOI,dp From： https://www.cnblogs.com/ydtz/p/17762677.html