本文出自 http://blog.csdn.net/shuangde800
题意
Petra和Jan分n个糖果,每个人轮流拿,一次只能拿一个,抽签决定谁先开始拿
每个糖果有两个值x,y, 如果Petra拿了会获得值x, Jan拿了会获得值y
Petra每次都选择对自己价值最大的(x最大)拿,如果有多个x相同大,选择y值最小的
Jan选择的策略是,要让自己最终获得的总价值最大, 并且在这个的前提下,要让Petra的值也尽量大
问最终他们获得的价值各是多少?
思路
这题的思维很巧妙
先只考虑Petra拿糖的情况,他的策略是贪心的,排序一下,可以知道他一定是从按照顺序依次选择下去的
看样例:
Jan
4 1
3 1
2 1
1 1
1 2
1 3
1 4
这个样例已经按照Petra的贪心策略排序好了,第一个被Jan拿先拿了,第二个一定会被Petra拿去。
接下来,如果Jan选择第3个,那么Petra就会拿第4个,如果Jam选除了第3个以外的任意一个,Petra都会拿走第3个。
所以,Jan每一次的选择策略是,要不要把Petra下一次要拿的那个给“抢过来”!
可以发现假设第一次是Jan开始拿(如果第一次是Petra拿,那么就从第二次开始算)
前1个,Jan最多可以抢1个
前2个,最多可以抢1个(如果拿了第1个,第2个一定会给Petra拿走,如果不拿第1个,那第1个就被Petra拿走了, Jan怎么也不可能拿走2个)
前3个, 最多可以抢2个
前4个,最多可以抢2个
前5个,最多可以抢3个
...(以下省略)
规律是,前i个,最多可以抢(i+1)/2个
所以,我们可以用状态f(i, j),表示前i个,抢j个的时候,自己的最大值
f(i, j) = max{ f(i-1, j), f(i-1,j-1) + y(i) | 当f(i-1, j-1)状态可达时);
另外,题目要有一个限制:在Jan最大价值的情况,让Petra的价值也最大。
那么,sum = x1+x2+x3+...xn, sum是所有糖果对Petra的价值之和
每当Jan抢了一个的时候,Petra的sum就会减少xi, 我们要让所有减少的xi之和最少,
这样,可以把物品x值看作是花费, y值看作是价值,目标是让Jan拿最大价值的情况下,花费最少
那么我们可以再维护一个数组cost(i, j)即可
代码
<script src="https://code.csdn.net/snippets/615.js" type="text/javascript"></script>
分享到:
相关推荐
Laravel开发-laravel-goodies 帮助器类和扩展,使Laravel中的REST框架更容易使用。
Sticky是nginx的一个模块,它是基于cookie的一种nginx的负载均衡解决方案,通过分发和识别cookie,来使同一个客户端的请求落在同一台服务器上,默认标识名为route (a)客户端首次发起访问请求,nginx接收后,发现...
Laravel开发-laravel-goodies .zip
目前的项目网站架构中使用了F5和nginx,F5用来做负载均衡,nginx只用作反向代理服务器。最近应客户的要求准备去掉F5,使用软负载。大家都知道nginx抗并发能力强,又可以做负载均衡,而且使用nginx对我们目前的网站...
gcp-goodies 博客文章系列的源代码和其他材料-GCP Goodies
Source directory "goodies" contains "goodies1", "goodies2" and "goodies3". usage example 1: %mksquashfs /home/phillip/test output_fs This will generate a squashfs filesystem with root entries "file...
Source directory "goodies" contains "goodies1", "goodies2" and "goodies3". usage example 1: %mksquashfs /home/phillip/test output_fs This will generate a squashfs filesystem with root entries "file...
球拍开发用品使Racket开发人员的生活更轻松的脚本。 plt-alias用于设置PLT环境变量的bash函数plt-bin重定向到适当二... 设置步骤示例: $ git clone [repo-url] racket-dev-goodies && cd racket-dev-goodies 将plt b
前端 npm-goodies 使用 JS 中的 npm 进行创造性编码、快速原型设计和前端开发的课程/示例。 它展示了现代实践的优势,如模块化、promise、函数式编程、browserify、Node、ES6 等。 这仍然是一项正在进行的工作。 ...
sticky-headers-recyclerview.zip,太多无法一一验证是否可用,程序如果跑不起来需要自调,部分代码功能进行参考学习。
iOS-Goodies:您最喜欢的iOS新闻,现已开源
elfeed-goodies:Elfeed的各种好吃的东西
回合-android-goodies 来自 Rounds Android 团队的可重用代码
Ouzo Goodies 它是什么 从提取的实用程序类,测试断言和。 我们与PHP 7.2及更高版本兼容。 如何使用它 几个例子。 : $ result = FluentArray :: from ( $ users ) -> map ( Functions :: extractField ( 'name' ...
Unity商店内这个组件的地址: https://assetstore.unity.com/packages/tools/integration/android-native-goodies-pro-67473 Unity游戏源码 , 完整的项目 , 适合学习和开发集成 , 调用安卓组件交互的神器 , 代码集成...
物品清单网页刮板适用于PHP的屏幕抓取和网络抓取库。 支持HTML / XML 浏览器工具Chrome在Bitbucket上的语法高亮显示使用JavaScript的浏览器推送通知后端API蓝图测试仪-从您的api蓝图文档中模拟为服务器高效使用...
tk-goodies提供了一组Tcl / Tk软件包,以简便而强大的方式构建GUI。
免责声明:资料部分来源于合法的互联网渠道收集和整理,部分自己学习积累成果,供大家学习参考与交流。收取的费用仅用于收集和整理资料耗费时间的酬劳。 本人尊重原创作者或出版方,资料版权归原作者或出版方所有,...
bash 好东西 用于 GIT 和其他命令行的 bash 好东西的集合! ###安装/升级 curl https://raw.githubusercontent.com/siddii/bash-goodies/master/install.sh | sh ###演示 ###通用命令/别名 serve # Runs a Python...
android-goodies 用于 Android 开发的助手和实用程序