3、（3,2）（2,2）（1,1）（2,2）（1,1）（1,1）（0,0）（0,0）（0,0）（1,1）（0,0）（0,0）（0,0）自顶而下构造浅析解“对策问题”的两种思路（4,3）（3,2）（2,2）（1,1）（2,2）（1,1）（1,1）（0,0）（0,0）（0,0）（1,1）（0,0）（0,0）（0,0）败败败败败败注：这里的胜败指的均是先手胜败。1如果一个状态没有子状态，是结局，则根据题目条件判定胜负浅析解“对策问题”的两种思路胜胜胜胜胜胜（4,3）（3,2）（2,2）（1,1）（2,2）（1,1）（1,1）（0,0）（0,0）（0,0）（1,1）（0,0）（0,
4、0）（0,0）败败败败败败注：这里的胜败指的均是先手胜败。1如果一个状态至少有一个子状态是先手败，则该状态是先手胜浅析解“对策问题”的两种思路胜败胜胜胜胜胜胜（4,3）（3,2）（2,2）（1,1）（2,2）（1,1）（1,1）（0,0）（0,0）（0,0）（1,1）（0,0）（0,0）（0,0）败败败败败败注：这里的胜败指的均是先手胜败。1如果一个状态的所有子状态都是先手胜，则该状态是先手败浅析解“对策问题”的两种思路“动态规划”或“记忆化搜索”空间复杂度O(N2)时间复杂度O(N3)（4,3）（3,2）（2,2）（1,1）（2,2）（1,1）（1,1）（0,0）（0
5、,0）（0,0）（1,1）（0,0）（0,0）（0,0）浅析解“对策问题”的两种思路思路一：一般性方法状态胜负规则扩展规则实现方法“一般性方法”是从初始状态出发，自顶向下，考察所有状态，逐步构造出“状态转移的拓扑结构”，有通行的胜败规则和实现方法，因此应用十分广泛。例如IOI96的取数字，IOI2001《Ioiwari》都可以用“一般性方法”来解决。浅析解“对策问题”的两种思路思路一：一般性方法状态列举影响结局胜负的所有因素，综合描述成“状态”。根据对局时状态之间的变化，自顶而下构造出“状态转移的拓扑结构”。胜负规则一个状态的胜负取决于其所有子状态的胜负。1如果一个状态
6、没有子状态，是结局，则根据题目条件判定胜负1如果一个状态至少有一个子状态是先手败，则该状态是先手胜1如果一个状态的所有子状态都是先手胜，则该状态是先手败浅析解“对策问题”的两种思路思路一：一般性方法扩展规则在某些场合下，还可以记录一个状态先手胜（负）的最大（最小）利益，以数值形式描述，再根据题目中相应的条件，构成新的具有针对性的推算规则。例如IOI2001《Score》一题就是用扩展规则解决的。实现方法1预先处理（关键）列举状态；构造“状态转移的拓扑结构”；动态规划或记忆化搜索求状态先手胜负。1对局策略依据已知的状态胜负，时刻把先手必败的状态留给对方。浅析解“对策问题”
7、的两种思路思路一：一般性方法“一般性方法”也有它的不足：基础“一般性方法”是以“状态转移的拓扑结构”为基础设计的。空间“一般性方法”要考察所有状态的先手胜负。如果状态数目过多，甚至是无穷多，那“一般性方法”就无能为力了。时间“一般性方法”还要通过胜负规则来研究状态之间的关系。如果状态过多，关系复杂，就可能导致算法效率下降。浅析解“对策问题”的两种思路思路一：一般性方法由此可见，“一般性方法”并不能解决所有的“对策问题”。于是，各种各样的针对单独问题的特殊解法应运而生，不妨总的称之为“特殊性方法”。为了弥补“一般性方法”的缺陷，“特殊性方法
