[SSLOJ2018 帮助]【状压dp】【贪心思想】

【题目】

【算法分析】

首先有一个显而易见的性质，我们如果拿起了一些书，那么对于同样高度的，就应该合在一起再放回去。如果分开放的话，不会使答案更优。

另外，如果我们拿起了一些高度为k的书，而书架上还有高度为k的书没被拿走。那么我们肯定会把这些书放到其中一个没被拿走的书的前面或者后面。显然，另外的方法不会比这更优。

于是，我们定义

F[i,j,k,l]表示决策完前i本书，已经被拿起的高度的书的集合为j(0<=j<2^8,二进制表示)，然后已经拿起了k本书，并且上一段的末尾为l的时候的最小混乱度。

转移有3种。

1、如果集合j里面包含有a[i+1]这样高度的书，那么把这些高度为a[i+1]的书全部放到a[i+1]前面。

2、我们把第i+1本书给拿起来，那么会出现两种情况。第一种：前面没有高度为a[i+1]且没有被拿起来的书。第二种：前面有高度为a[i+1]且没有被拿起来的书。

首先一个问题就是对“是否存在没动的高度为a[i+1]的书”的判定。我的判定方法是这样的：如果前面有高度为a[i+1]的书，而且j这个被拿起的书的集合里没有高度为a[i+1]的书，那么肯定前面有没被“拿起的书”。否则必然没有。

对于第一种情况，我们把被拿起的第i+1本书放进集合j里面。

对于第二种情况，我们把被拿起的第i+1本书放到前面没被动的，高度为a[i+1]的书的后面。

3、不拿书也不放书，就直接算~

最后由于空间巨大，要用一下滚动数组。。。

【时间复杂度】

O(n*2^8*m*8)

【空间复杂度】

O(2^8*m*8)

【其它】据说有O(n*2^8*m)的算法。。。求好心人发一下。

【CODE】

C++ CODE   :SSL2018 1 2 3 4 5 6 7 8 910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061 #include