HDU4532 安排座位

传送门

题意

给出$n$种颜色的小球,每种$a_i$个,求使得任意同色球不相邻的方案数。

题解

这是一类经典问题,考虑用dp解决。

不妨设$dp[i][j]$表示前$i$种颜色,有$j$对冲突的方案数,那么答案就是$dp[n][0]$。

设当前考虑到第$i$种颜色,前面的球的总数为$sum$,现在把这的颜色分为$k$段$(k\leq a[i]$且$k\leq sum+1)$。

段与段之前不会产生冲突,那么产生新的冲突对为$a[i]-k$。

在这$k$段种选择$l$段插入之前的冲突对中$(l\leq k$且$l\leq j)$,剩下的$k-l$段插入其他的位置。

新状态冲突的对数是$j-l+a[i]-k$,这样做的总方案数为$\binom{a_i-1}{k-1}\cdot \binom{j}{l}\cdot \binom{sum+1-j}{k-l}$

得到转移
$$
dp_{i,j-l+a_i-k}=\sum dp_{i,j} \cdot \binom{a_i-1}{k-1}\cdot \binom{j}{l}\cdot \binom{sum+1-j}{k-l}
$$

以上考虑的是可重排列,也就是说小球不同当且仅当颜色不同。此题是不重排列,答案就要乘上$\prod a_i!$。

复杂度

复杂度为$O(n\sum(a_i)\cdot max(a_i)^2)$。对于一般的序列,复杂度为$O(n^3)$。

因为如果$max(a_i)$变大,那么$\sum(a_i)$的规模就要变大,所以一般出不了很大。而如果只有一个$a_i$很大,那么$max(a_i)^2$这个地方是跑不满的,所以还是比较快的。

代码

Leave a Reply

Your email address will not be published. Required fields are marked *