P1386 座位安排——被想歪了的dp

· · 个人记录

初见思路

寻找研究对象，结果找错了找成最终排列，然后求最终排列的方案数，然后试图先dp找出不需要约束时的答案，最后再把约束并回去

于是一顿繁复的操作，写出来个很酷的 O(n^2) 解法，发现约束并不回去了

再看一眼

事实上，我们的研究对象确实是方案，是合法方案，所以找最终排列对我们而言只是一个手段，但是是变成那样找不到原本的位置，约束更难加了

所以考虑什么时候方案合法

发现当方案非法时，有人出界了，就一定有位置被空出来了

每个位置只能由下方的序号找到，所以对于一个位置，它的下方必须能填满

于是带着这个约束条件，就可以开始dp了

设 dp_{i,j} 为考虑到编号 i ，有 j 个数 \le i 时的方案数

首先要考虑钦定的问题，如果有人的方案被钦定了，那么它就不能成为被选择的那个

其次要考虑枚举的范围，显然最大只能枚举到n-大于自己的被钦定的数

然后状态转移方程就出来了

dp_{i,j}=\sum_{k=0}^{j-sum_i}dp_{i-1,j-k-qd_i}\times C^{j-sum_i}_k

最后要注意多测清空