看到第一眼就发觉是壮压DP 然后就三进制枚举子集吧。 这题真是壮压入门好题。。。 对于dp[i][j] 表示第i行，j状态下前i行的分配方案数。 那么dp[i][j]肯定是从i-1行转过来的 那么由于不能挨着放，那么我们肯定是枚举i - 1行状态时不能包含j的任何一位。 那么只要令k = ((1 << n) - 1) ^ j，k中肯定就不包含j的位了 是这样枚举k的子集 in