我是这样做的,dp + 缩小数据规模

用一个bool数组存放两人手中的石子的可能的差，一开始的时候可能的差为{0};
若此状态中有一个可能差为{....... ，a,...}那么取了一个价值为v的石子后集合变成
{....., a + v,a - v,.....}
如果 a - v < 0. a - v 变成 v - a.

然后我用两种不同的方法缩小数据规模，
一，当 a + v > 60  将 (a + v) % 60后放入集合 （bool数组）。

二，当a + v > 60 将 a + v不给予考虑。

最后判断集合中是否有0，也就是两人手中的价值相差0，
true  can 
false can't

这两种方法都AC了，
但是这些是有明显不同的，
第一种是认为 任何总和 60 价值的石子都可以分成两堆价值和为30的石子，因为取模了，所以可能导致
一些无法分割的情况输出可分割

第二种可以认为是种剪枝，认为当一种分配方案过程中，当一方手中的石子比另一方多60或者更多的话这
种方案明显不合理，去掉。如果这种方法错误的话，它可能丢掉一些可行解决。

但是两种方法都AC了，why?

• 你可以对这两个方法测试一下，是不是所有数据解都一样的 (630) hawk 2005-06-12 10:14:28
  • 测了很多数据，确实是一样的，好象缩小到30也行！ (59) queyue2004 2005-06-12 10:58:52
    • 我就%30 (0) frkstyc 2005-06-12 10:59:10
      • 也就是说任何价值和为30的石子都可以分成两堆价值为15的石子？这个价值最少能取到多少呢？ (0) queyue2004 2005-06-12 11:02:33
      • 我不是%30 (0) frkstyc 2005-06-12 14:04:28
• 第一种方法不对，第二种正确 (485) xfxyjwf 2005-06-12 13:56:55
  • Re:第一种方法不对，第二种正确 (81) xfxyjwf 2005-06-12 14:17:45
    • Re:第一种方法不对，第二种正确 (20) xfxyjwf 2005-06-12 14:23:36
  • 谢谢了，这两组数据就测出错误了。：） (0) queyue2004 2005-06-12 19:38:02