【JZOJ3853】【NOIP2014八校联考第2场第2试9.28】帮助Bsny(help)
2024-09-06 12:33:25
EVRT
Bsny的书架乱成一团了,帮他一下吧!
他的书架上一共有n本书,我们定义混乱值是连续相同高度书本的段数。例如,如果书的高度是30,30,31,31,32,那么混乱值为3;30,32,32,31的混乱值也为3。但是31,32,31,32,31的混乱值为5,这实在是太乱了。
Bsny想尽可能减少混乱值,但他有点累了,所以他决定最多取出k本书,再随意将它们放回到书架上。你能帮助他吗?
1≤k≤n≤100,注意所有书本高度在[25,32]。
COMEHERE
首先如果考虑动态规划的话,会设置f[i][j],表示表示前i本书中,有j本书被抽走。
再想想会加上第三维k,表示没被抽走的书中最后一本书的高度是k。
显然转移方程有两种:
1.不抽走当前这本书,容易推;
2.抽走当前这本书,但要放在哪呢?
(1)放在另一本和这本书的高度相同的书旁边;
(2)放在开头,自成一家。
讨论第(1)种情况,
–如果这所谓的“另一本”在这本书的前面,由于书的高度只有8种,所以考虑加上第四维l,表示没被抽走的书的高度出现情况压位(28)。
–如果这所谓的“另一本”在这本书的后面,容易得出这本书后面是否有另一本相同高度的书,预处理出来就可以。
设f[i][j][k][l],表示前i本书中,有j本书被抽走,没被抽走的书中最后一本书的高度是k,没被抽走的书的高度出现情况压位(28)表示l,的最小混乱度。
最新文章
- 移动端web开发总结
- 获取Graphics对象的方法
- Odoo创建数据库时出现的问题 DataError: new encoding (UTF8) is incompatible with the encoding of the template database (SQL_ASCII)
- tar
- 使用PHP导入和导出CSV文件
- 海蜘蛛WiFiDog固件 MTK7620 OEM,带云AC功能、探针、广告插入,MTK7620解包打包维修默认参数
- 161201、常用 SQL Server 规范集锦
- rcp(插件开发) 如何查找自己定义的扩展点
- ZigZag Conversion2015年6月23日
- CKEditor与dotnetcore实现图片上传
- bzoj 3999: [TJOI2015]旅游
- SpaceVim中vimproc的vimproc_linux64.so未找到
- C# 属性(Property)和字段(Field)的区别
- 剑指offer——python【第15题】反转链表
- 【JVM】-NO.110.JVM.1 -【JDK11 HashMap详解】
- C#的RSA加密解密签名,就为了支持PEM PKCS#8格式密钥对的导入导出
- 【WPF】数据验证
- [Oracle]Oracle之Chr函数返回
- 深入理解java虚拟机(十一) 方法调用-解析调用与分派调用
- 调用start()与run()的区别