一开始还以为又要整什么\(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\)的情况