hdu4778（状态压缩dp）
2024-08-30 18:25:22
题意：
有G种颜色的宝石，共B袋。两个人轮流拿宝石，每次从B袋中拿一袋，把其中的所有宝石倒入一个公共容器，每袋宝石只能取一次。
当容器中有S个相同颜色的宝石时，将失去这S个宝石，当前操作者得到一个魔法石，每次得到一个魔法石，作为奖励，他都可以再次拿一袋宝石倒入容器。
双方都想让自己的魔法石尽量多，Alice先手，问在最优操作下，Alice 和 Bob的魔法石差是多少。
0 <= B <= 21, 0 <= G <= 8, 0 < n <= 10, S < 20。
分析：
因为数据很小，所以考虑用状态压缩来表示
对于状态S，若某位为0，则说明该位的袋子没有丢到容器中，若某位位1，则说明该袋子已经丢到了容器中，f[S]表示S状态下，先手-后手的最大值
显然答案ans=f[0]
考虑初始情况f[(1<<n)-1]=0（因为这表示所有袋子都已经丢到了容器中，在剩余的袋子中，先手后手都无法取，0-0=0）
枚举状态S的每一个数字0的位置i
f[S]由f[S|1<<i]逆推得到
若将i丢进容器，没有获得魔法石，那么f[S]=max(f[S],-f[S|1<<i]) （因为交换了先手后手顺序）
若将i丢进容器，获得了魔法石，那么f[S]=max(f[S],f[S|1<<i]+丢进i获得的魔法石) （因为获得了魔法石，所以先手仍旧是先手）
注意dp过程中计算某个位置的贡献，这是可以预处理的
复杂度O(2^B * B * G)
最新文章
- iOS开发--引用计数与ARC
- mysql 命令行操作1
- hibernate(七) hibernate中查询方式详解
- [Asp.net 5] DependencyInjection项目代码分析
- [NOIP2010] 提高组 洛谷P1541 乌龟棋
- 51nod1201 整数划分
- android Theme使用三
- UART RS232 的CTS与RTS
- （原）error LNK2038: 检测到“_ITERATOR_DEBUG_LEVEL”的不匹配项: 值“0”不匹配值“2”
- 搭建开发框架Express，实现Web网站登录验证
- Spring 使用AspectJ的三种方式
- SPOJ DIVCNT2
- 整理oracle 树形查询
- mysql优化-数据库优化、SQL优化
- Android Studio_更新Gradle
- sharpsvn 继续,解决文件locked 问题,
- 20155205《Java程序设计》实验五（网络编程与安全）实验报告
- MySQL数据库与表的增删改查
- Codeforces343D(SummerTrainingDay06-F dfs序+线段树)
- C# 批量上传