小k的硬币问题_牛客博客

题解：不会做，先扔官方题解

这道题要用到博弈论的思维来解答，先来分析每一堆硬币，数量为1~10，

当数量为1时，没法选择策略，只能拿1个，

当数量为2~5时，先选的人可以选择拿走n-1个，下一堆硬币有优先选择权，也可以选择拿走n个，下一堆硬币后选，

当数量为6时，只有一种策略，就是拿走5个（因为拿走5个以下时，另一个人就能决定你下一堆硬币的先后手，题目已经申明两个人都足够聪明），这是下一堆硬币先选，

当数量为7~10时，可以选择拿走n-6个，此时对方只能拿走5个，然后自己拿走剩下的1个，下一堆硬币后选，也可以直接拿走5个，让对方决定自己下堆硬币是先手还是后手。

因为考虑到一开始后手的人有一次一次性拿走一堆硬币的机会，所以以该角色进行倒推（倒推的话，每个人在选择的时候都能看出自己之后怎么选才是最合适的），分为4个状态，

1.该堆硬币有优先选择权，且有一次机会已经用过，

2.该堆硬币没有优先选择权，且一次机会已经用过，

3.该堆硬币有优先选择权，且有一次机会，

4.该堆硬币没有优先选择权，且没有机会，保存每种状态下能拿到的最多的硬币数量。

从后往前开始逆推时，要考虑的如果有一次机会的话，可以通过这一次机会来改变自己下一堆硬币的先后手，且如果是后手，对方只会选择让你拿到最少硬币的策略。当逆推结束是，第二种状态能拿到的最多的硬币数量就是，后手这个角色能拿到的最多的硬币数量。