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]的答案。
详见代码
最新文章
- 软件工程(FZU2015)赛季得分榜,第八回合
- NOIP模拟赛 行走
- 使用MegaCli和Smartctl获取普通磁盘
- 操作无效:已关闭 Lob。 ERRORCODE=-4470, SQLSTATE=null
- 使用Spring的Property文件存储测试数据 - 编写测试和调用测试数据
- Performance testing of web application
- bzoj2071: [POI2004]JAS
- linux命令中";|";管道流的意思
- 钢管下料问题2(剩余材料最少)lingo求解
- SVN提交出现“<; <; <; <; <; <; <; .mine’无效,路径中具有非法字符”的问题
- jvisualvm中VisualGC插件提示:不受此JVM支持
- PCA whitening
- RabbitMq中的消息应答与持久化
- 10分钟搭建 App 主流框架
- jdk1.8.0_45源码解读——Set接口和AbstractSet抽象类的实现
- SimpleDraweeView 设置圆角不生效问题
- MOSFET 线路 12V 无法工作的问题(等待回复)
- SteamVR Unity Plugin - v2.0.1中的InteractionSystem
- bzoj1426(洛谷4550)收集邮票
- python uwsgi 部署以及优化
热门文章
- Linux Cgroup v1(中文翻译)(4):Block IO Controller
- Docker容器固定ip
- redis击穿,穿透,雪崩,分布式锁,api(jedis,luttuce)
- C# 读写文件从用户态切到内核态,到底是个什么流程?
- [pwn基础]Pwntools学习
- UiPath条件判断活动If的介绍和使用
- 用Python实时获取Steam特惠游戏数据,我看看谁的钱包还有钱
- Windows对拍系统
- 攻防世界MISC进阶区 61-63
- STM32与物联网01-ESP8266基本操作