洛谷P3052题解
2024-10-19 12:23:02
看起来非常简单,但是细节多的一批的状压DP入门题。
我设 \(f_i\) 为 \(i\) 状态时最小分组数, \(g_i\) 为 \(i\) 状态时最后一组剩余空间。
对于每一个 \(i\) ,枚举每一个 \(1\le j\le n\) 且 \(j\) 不在 \(i\) 内, 即 \(i \& (1<<(j-1))=0\) 。然后分类讨论:
- \(j\) 可以放在最后一组中, \(f_{i | (1<< (j-1))}=\operatorname{min}\{f_{i | (1<< (j-1))},f_i\}, g_{i | (1<< (j-1))}=\operatorname{max}\{g_{i | (1<< (j-1))},g_i-a_j\}\) 。
- \(j\) 不能放在最后一组中, \(f_{i | (1<< (j-1))}=\operatorname{min}\{f_{i | (1<< (j-1))},f_i+1\}, g_{i | (1<< (j-1))}=\operatorname{max}\{g_{i | (1<< (j-1))},W-a_j\}\) 。
初始状态:\(f_0=1,g_0=W\),就是开一个空的组。其他的 \(f_i\) 赋 INF
。
答案就是 \(f_{(1<<n)-1}\) 。
代码
最新文章
- Linux查看系统状态命令
- 2.1 python使用MongoDB 示例代码
- webstorm 10 出现不能run cordova项目
- Spark入门实战系列--2.Spark编译与部署(上)--基础环境搭建
- [转]NopCommerce How to code my own payment method
- UI中经常出现的下拉框下拉自动筛选效果的实现
- [ javascript css clip ] javascript css clip 的奇思妙想之文字拼接效果
- Caffe学习系列(6):Blob,Layer and Net以及对应配置文件的编写
- [SAP ABAP开发技术总结]采购、销售、生产简单业务流程
- UML工具选择
- Google Code Jam 2009, Round 1C C. Bribe the Prisoners (记忆化dp)
- E-BOM和M-BOM的区别
- Jenkins 快速搭建持续集成环境
- Eclipse总是自动关闭
- Spring事务管理与数据库隔离级别的关系(Spring+mysql)
- 在VS2015中用C++编写可被C#调用的DLL
- Centos7 网络报错Job for iptables.service failed because the control process exited with error code.
- (原)caffe中的conv
- java中random()函数用法介绍
- 关于js事件执行顺序小技巧