P3507 [POI2010] GRA-The Minima Game

发布时间 2023-09-11 08:10:47作者: FOX_konata

原题

一开始还以为又要整什么\(SG\)函数就直接放弃思考了,后来看了题解才发现是贪心+\(dp\)

首先先对\(a\)从小到大排序

首先先说一个错误的贪心:每个人都只选最大的那一个数。这显然是错误的(笨笨的我起初甚至是这么想的),因为玩家可以把一些可能让对方变优的数自己先选掉,来使自己走向更优的策略。

因此这里有一个贪心:每个人只会选没选过的最大的若干个连续的数。首先最大显然。如果不选连续的数,那\(B\)就可能会把你没选过的最大的数选掉,也是不优的

因此我们设\(dp_i\)表示选前\(i\)个数,让先手值最大,值是多少

可以得出递推方程:\(dp_i = \max_{j=1}^{i}{a_j-dp_{j-1}}\),大致意思就是枚举当前玩家上一个位置选到哪。显然维护一个前缀最大值即可

最终复杂度\(O(n)\)

\(p.s.\) \(a\)不从大到小排序的原因是这样\(dp\)可能会出现先手不是\(B\)的情况