24OJ #28. 【2017省选模拟】取石子 DP

应OJ要求,题面已删除。

考试的时候并没有想到是dp,然后题答宛如一个智障在写模拟退火,然后调了半天参数放弃治疗了。然后就没啥时间了。GG

我们首先可以大概认为k是没有什么用处的。因为每个人最多一次只会取一个石头,因为每个人可能取到的位置是确定的,自己的嘛,当然拿的越少越好。

最小的点必然是必输状态,因为你把旗子放出去,人家给你放回来,你的石头少,消耗不起,然后会先GG。

我们考虑我们在挪动旗子的时候只能旗子往小的地方移动,因为如果向大的地方移动,人家还可以给你移动回来你消耗不起。

所以我们可以把石头数目进行排序,然后从小到大来进行DP。

根据博弈论的基本常识,一个点他的后继状态中有必败状态,那么他就是必胜的,否则是必败的。最初我们可以初始化所有点都是必败的。

对于两个点点权相同的情况,我们考虑,跟你往大的移动一样,最后还是你先没有,所以跟大的一样处理。

发表评论