BZOJ 1783 [Usaco2010 Jan]Taking Turns

发布于 2017-06-21  224 次阅读


题目链接: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 我们并不需要记录所有状态... 这是一个小优化

优化后

 


一个非常弱的准退役OIER