资源描述：
《算法合集之《从“k倍动态减法游戏”出发探究一类组合游戏问题》》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、从“k倍动态减法游戏”出发探究一类组合游戏问题上海市上海中学曹钦翔指导教师：上海市上海中学毛黎莉目录一：引言二：问题的提出三：动态规划的通式解法四：基于动态规划的优化4.1利用单调性解决“k倍动态减法游戏”五：不基于动态规划的思考5.2利用贪心解决BOI2008gameNP状态所谓N状态，是指当前即将操作的玩家有必胜策略（N来源于Nextplayerwins.）。所谓P状态，是指先前刚操作完的玩家有必胜策略（P来源于Previousplayerwins.）。定理：P状态的一切后继都为N状态，N状态拥有至少一个后继是P状态。通式动态规划解法步骤1：把所有“胜利终止状态”标记为
2、P状态，“失败终止状态”标记为N状态。步骤2：找到所有的未定状态中，所有后继都被确定是N状态的状态，设置为P状态。步骤3：找到所有的未定状态中，可以一步到达P状态的状态，都设置为N状态。步骤4：若上两步中没有产生新的P状态或N状态，程序结束，否则回到步骤2。时间复杂度——所有状态的决策数之和k倍动态减法游戏有一个整数S（>=2），先行者在S上减掉一个数x，至少是1，但小于S。之后双方轮流把S减掉一个正整数，但都不能超过先前一回合对方减掉的数的k倍，减到0的一方获胜。问：谁有必胜策论。K=2A第一回合减去2A第二回合减去1B第一回合减去4A获胜通式解法NP(m,n)表示S还剩
3、下m且接下去即将操作的玩家最多能减去n的状态，则初始状态为NP(S,S-1)。规定，若在NP(m,n)状态下，即将操作的玩家必胜则NP(m,n)=1，否则NP(m,n)=0。若用动态规划计算所有NP(m,n)，则判定胜负的时间复杂度为O(n3)。优化1状态单调性状态NP(m,n)是关于关于n单调不减的。记f(m)=min{n
4、NP(m,n)=1}优化1NP(m,n)=0当且仅当对于任意r=1,2,3…n有m-r>0且NP(m-r,kr)=1。若n0=f(m)，则NP(m-n0,kn0)=0且NP(m-n0+1,k(n0-1))=1若n0=f(m)，则f(m-n0)>kn0且
5、f(m-(n0-1))<=k(n0-1)。动态转移方程：f(m)=min{n
6、f(m-n)>kn}时间复杂度：O(S2)优化2—决策单调性优化2—决策单调性所有这些直线是平行的随着m增大逐渐向下向右移每一堵墙都是固定的、右端有界的用栈储存“墙”优化2—决策单调性逐个检验栈中的“墙”若某堵“墙”不能挡住从(m,0)格子出发斜率为k-1的直线，那么该“墙”出栈否则，若这堵“墙”能挡住斜线，则循环结束并得出f(m)的值。最后，根据f(m)可确定一堵新“墙”的位置和长度，新“墙”入栈。时间复杂度：O(S)BOI2008game一个n*n的棋盘，每个格子要么是黑色要么是白色。白格子是
7、游戏区域，黑格子表示障碍。指定两个格子AB，分别是先手方和后手方的起始格子。A和B这两格子不重合。游戏中，双方轮流操作。每次操作，玩家向上下左右四个格子之一走一步，但不能走进黑色格子。有一种特殊情况，当一方玩家，恰好走到当前对方所在的格子里，他就可以再走一步（不必是同一方向），“跳过对手”。胜负的判定是这样的，若有一方走进对方的起始格子，就算获胜，即使是跳过对方，也算获胜。通式解法用(x1,y1,x2,y2)表示状态。其中(x1,y1)是A的当前位置，(x2,y2)是B的当前位置。另外，还需要一位状态表示当前的操作这是A或B。因此，状态总数至少为O(n4)个，尽管每个状态的
8、状态转移代价为O(1)，但总时间复杂度为O(n4)，太高了。而且状态数为O(n4)也意味着动态规划已经没有优化的余地，算法的设计必须跳出动态规划的框架。贪心思路“先”贪心的信号两人都应沿着两起始点间的最短路径走注意到，两个人需要走的路程是相等的所以如果没有“跳过对手”的规则，先行者将必胜！结论：如果先行方A能避免B“跳过A”，则A获胜；如果后手方B能确保在最短路径上“跳过A”，则B获胜。BOI官方解答记d为AB之间最短路的距离。若d为奇数，A必胜！所以只要考虑d时偶数的情况用数组LAi存贮，在AB最短路径上，且与距离A为i的格子。记NP_A[i,j,k]表示，轮到A操作
9、时，A在LAi中的第j个格子上，B在LAd-i中的第k个格子上的状态。NP_B[i,j,k]表示，轮到B操作时，A在LAi+1中的第j个格子上，B在LAd-i中的第k个格子上的状态。BOI官方解答的错误BOI的官方解答中认为，数组NP_A[i,j,k]和数组NP_B[i,j,k]表示的状态总数为O(n3)数量级。但是，形式上的三位数组并不等于包含的数据为立方阶。事实上，这三维都不是O(n)的。进一步的优化首先，不属于任何一个数组LAi的白格子等同于黑格，所以把它们涂黑。观察得到结论：对每一个i而言，数组LAi中的格
