20个问题（状压dp）
2024-09-04 16:14:39
20个问题（状压dp）
有n(<=128)个物体，m(<=11)个特征。每个物体用一个m位01串表示，表示每个特征是具备还是不具备。我在心里想一个物体，由你来猜。你每次可以询问一个特征，然后我会告诉你：我心里的物体是否具备这个特征。当你确定答案之后，就把答案告诉我。如果你采用最优策略，最少需要询问几次就能保证猜到？
设s表示已经询问的特征集，用a来表示确认一个物品具备的特征集，\(d(s, a)\)表示还需询问的最小次数。如果下一个提问的对象是特征k（这就是决策），那么询问次数为：\(max\{d(s+\{k\}, a+\{k\}), d(s+\{k\}, a)\}+1\)。考虑所有的k，取最小值即可。
为什么这样取最大值最小值呢？由于题目要我们能保证猜到，所以万一这个物品没有，万一这个物品有的情况，都要考虑进去，因此里面是max。而又因为题目让我们采用最优策略，在保证猜到的前提下猜最少次数，所以我们要寻找最优的决策，所以外面是min。
代码。。煤油。
最新文章
- Golang类型转换
- 克隆虚拟机重启服务时 Error:No suitable device found: no device found for connection "System eth0"
- sql server 警报管理，实时监听数据库动向，运筹帷幄之中
- php大力力 [045节] 兄弟连高洛峰 PHP教程 2014年[已发布，点击下载]
- Android主流UI开源库整理（转载）
- C# 文件读写FileInfo
- ie8解决F12问题
- C# TcpListener的编程要点
- vs自带服务测试工具
- MVC中的Ajax（AjaxHelper）
- Hdu 1016 Prime Ring Problem (素数环经典dfs)
- Linux中搭建Maven私服
- 史上最简单的SpringCloud教程 | 第六篇: 分布式配置中心(Spring Cloud Config)
- 【Codeforces】Gym100633 D. LWDB
- 使用js实现思维导图
- LeetCode 题解之 Two Sum
- MYSQL判断不存在时创建表或创建数据库
- 从零实现Lumen-JWT扩展包(序):前因
- HTTP 代理服务器技术选型之旅
- this关键字制定对象的属性