CF2066D2
Xycxxx
·
·
题解
延迟钦定。
考虑能放飞机的楼层是一个后缀，设 f_{i,j,k} 表示前 i 个飞机，最低的可以放飞机的楼层为 j，第 j 层看到了 k 个飞机。则答案显然为 f_{m,n,c}。
对于 k<c 的情况，能放飞机的楼层为 [j,n]，先不考虑这个飞机在哪个楼层放的，转移有：
f_{i,j,k}\to f_{i+1,j,k+1}
对于 k=c 的情况，能放飞机的楼层为 (j,n]，考虑转移到 j+1 后 j+1 看到了几个飞机，直接钦定 j 放的飞机数 x 即可，有：
f_{i,j,c} \times \dbinom{c-\sum_{p=j}^n\sum_{q=1}^i[a_q=p]}{x-\sum_{p=1}^i[a_p=i]} \to f_{i,j+1,c-x}
预处理一下组合数即可，复杂度 \mathcal{O}(nmc)。