本文主要是介绍Codeforces Round #585 (Div. 2) E. Marbles (状压DP),BZOJ大理石(同一道题)题解,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
题意
林老师是一位大理石收藏家,他在家里收藏了n块各种颜色的大理石,第i块大理石的颜色为ai。但是林老师觉得这些石头在家里随意摆放太过凌乱,他希望把所有颜色相同的石头放在一起。换句话说,林老师需要对现有的大理石重新进行排列,在重新排列之后,对于每一个颜色j,如果最左边的颜色为j的大理石是第l块大理石,最右边的颜色为j的大理石是第r块大理石,那么从第l块大理石到第r块大理石,这些石头的颜色都为j。
由于这些大理石都比较重,林老师无法承受这些大理石的重量太久,所以他每次搬运只能交换相邻的两块大理石。请问,林老师最少需要进行多少次搬运?
第一行输入一个数字n(2≤n≤4*10^5),表示大理石的总数。
第二行输入n个数字a1,a2…,an(1≤ai≤20)表示第i块大理石的颜色为ai。
输出一行一个数,即林老师最少需要搬运的次数。
给你一个序列,你可以交换相邻的两个数,要达到一个要求,所有相同的数都相邻,问你交换次数最少是多少。
题解
别人的:https://www.cnblog*.com/Lis-/p/11537603.html
上面的大佬解释的不是很清楚,因此我来详细地写一篇。
我们必须分析出一些结论。
在交换数之后,必然形成的是相同数字“聚居”的一条数链,所以不同数字形成的唯一连续子段都有严格的先后关系。如果所有数字A要在B后面,有i<=j,且a[i] = A,a[j] = B,在交换时是否一定会有某时刻a[i]要与a[j]相邻并交换?。。。。。。答案是一定的,相当于一次交换只能左或右移动一位。
那么反过来,如果交换左右相邻的两数不同,则最后左边的数一定全是在右边的数左边的......
如果最后形成的是:............2 2 2 2 ,即所有的4个 2 都在最后,则在第一个2和最后一个2之间的 !=2 的数(牵连着最后一个2之后同种的数)肯定都在“............”里,换言之,可以通过求这些数的数量,即分别求a和b之间相邻交换的次数来求出答案(?)
这是一道较复杂的题,但是数据很小(种类数<=20),曾经某位大佬说过,这种小数据要么搜索,要么状压DP。我用的是状压,但状态要怎么表示呢?显然,我们不能把20个种类最终的"站位"用二进制表示,但是20个种类最终的"站位"就决定了答案,所以我们可以只记录最终序列的前缀的组成部分(晕),就是表示若干种类的所有数堆在前面。。。
举个例子:
原数组:1 1 1 2 2 2 3 3 3 4 4 4 5 5......
k = 0101
dp[k](dp[0101])就表示排在前两组的是所有的1和3,k表示的状态要么是{1 1 1 3 3 3 ......},要么是{3 3 3 1 1 1 ......},即dp[k]就表示在这两种状态中交换次数最少的一种状态的交换次数。状态表示得如此不明确,但是却可以在求 dp[0111] 并假设2在最后时应用dp[0101],求出dp[0111]的答案。
详见代码
期年之后的下一篇:消防局的设立
这篇关于Codeforces Round #585 (Div. 2) E. Marbles (状压DP),BZOJ大理石(同一道题)题解的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!