题解 P3153 【[CQOI2009]跳舞】

这是一道动态规划题目。

首先，我们可以想到一个状态 $f_{i,j}$ 表示前 $i$ 个人跳舞，第 $i$ 个人跟第 $i-1$ 个人跳的舞种为 $j$ 的方案数。

然后，我们可以得到状态转移方程：

$$f_{i,j}=\sum_{k\neq j}f_{i-1,k}$$

即第 $i$ 个人可以跳除了 $j$ 以外的任何一种舞，因此我们枚举前面的人跳的舞种，转移即可。

最后，答案即为 $\sum_{i=1}^{n}\sum_{j=1}^{m}f_{i,j}$，表示前 $i$ 个人跳任何一种舞的方案数之和。

时间复杂度为 $O(nm^2)$，可以通过此题。