web analytics

BZOJ1231[Usaco2008 Nov]mixup2 混乱的奶牛 状态压缩DP

题目链接http://www.lydsy.com/JudgeOnline/problem.php?id=1231

分析:

因为N<=16。所以所有状态是可存范围内的。

使用二进制来存放某个数的存在的状态。

由于这道题我们只需要知道有多少情况存在,所以我们不需要去存什么数在什么位置。

这道题限制相邻两个数。所以我们只需要存:在选取了几个数的状态下,然后最后一个数是谁,一共有多少种排列。

设f[i][j]

其中i表示最后一个数是谁。

其中j表示当前的选取的几个数。

f[j][i|(1<<(j-1))]+=f[q][i]

PS:注意开long long int

 

Post a Comment

You must be logged in to post a comment.