BZOJ 1783 [Usaco2010 Jan]Taking Turns


题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=1783

题意:一排数,两个人轮流取数,保证取的位置递增,每个人要使自己取的数的和尽量大,求两个人都在最优策略下取的和各是多少。


一个挺有意思的 DP 题,我们正着考虑是不好确定选了哪个数的,但是最后一个数是一定被选了的,这启示我们可以倒着考虑问题:

设\(f_i\) 表示对于第 i 个数,先手的最大收益,\(g_i\) 表示后手最大收益,那么我们考虑对于第 i 个数,先手只有选和不选两个选择,如果选了,先后手调换,如果不选,直接 i++,因为先手还要考虑下一个数

那么先手什么情况下会选呢,显然,当\(g_i+a_i>=f_i\) 才会选,意为获得了 i 这个数,同时获得后手收益,那么问题就很好解决辣

我们考虑到\(f_i\),\(g_i\) 只与\(f_i+1\),\(g_i+1\) 有关系,所以对于 f 和 g 我们并不需要记录所有状态... 这是一个小优化

优化后

 

声明:zgz233|版权所有,违者必究|如未注明,均为原创|本网站采用BY-NC-SA协议进行授权

转载:转载请注明原文链接 - BZOJ 1783 [Usaco2010 Jan]Taking Turns


一个oier的博客 |注册功能过几天就修| 博客搬家啦,现在跑的飞快!

标签: , ,