回复：（ConZhang）一道ACM的题，请教各位？
有时候做题是看灵感的，包括对数字的敏感，这题就是这样（至少我是这样做出来的）
我来分析一下，首先，这是一道博弈问题，看上去像一种Combinatorial Game
参考一下《Game Theory》--Thomas S. Ferguson
What is a Combinatorial Game? We now define the notion of a combinatorial
game more precisely. It is a game that satisfies the following conditions.
(1) There are two players.
(2) There is a set, usually finite, of possible positions of the game.
(3) The rules of the game specify for both players and each position which moves to
other positions are legal moves. If the rules make no distinction between the players, that
is if both players have the same options of moving from each position, the game is called
impartial; otherwise, the game is called partizan.
(4) The players alternate moving.
(5) The game ends when a position is reached from which no moves are possible for
the player whose turn it is to move. Under the normal play rule, the last player to move
wins. Under the mis`ere play rule the last player to move loses.
If the game never ends, it is declared a draw. However, we shall nearly always add
the following condition, called the Ending Condition. This eliminates the possibility of
a draw.
(6) The game ends in a finite number of moves no matter how it is played.
我们可以考虑动态规划求解这个问题，但是砝码的个数不足以刻画整个问题，因此我们需要加上一个参数，就是最大可以取走的砝码个数。
这样就需要一个二维的数组来存储。我们看到n的规模(1,100000)不允许我们使用n^2级的空间，先写一下状态转移方程看有没有办法节省。
dp[n][k]中n表示当前砝码的个数，用k表示当前可以最大取走的砝码个数。用dp[n][k]=1表示当前状态是一个先手必胜状态,dp[n][k]=0表示当前状态是一个先手必败状态。
dp[n][k]= !(dp[n-1][2*1]&&dp[n-2][2*2]&&...&&dp[n-k][2*k])
其中k>=n的状态显然是先手必胜状态，n<0的状态是没有意义的，这些我们暂时先不考虑。
总之根据这个状态转移方程是没办法节省空间。
然后我写了一个小规模的程序把2到100的结果打印出来，发觉是有规律的，2，3，5，8，13，21，...是NO，其他的是YES。如果你还看不出的话，我加上两个数你就看出来了，1,1,2,3,5,8,13,21,...
至此，我们当然可以大胆猜测～！◎＃￥，然后提交，AC，over。
2007-08-15 08:12
