dreamangel

http://acm.pku.edu.cn/JudgeOnline/problem?id=1740
题目大意：有N堆石头，每堆石头数目在1到100之间，最多有10堆，两人分别取走石头。取石头的规则是：每次只能从1堆中取，每次取走至少1个，取过后还可以把这堆的石头任意分配到其它堆上(这些堆必须有石头)，当然也可以不分配。问给定这些石头堆的情况，两人轮流取，谁先取完谁胜利，问是先取的胜利还是后取的胜利，求双方最优策略？
首先讨论石头堆两堆两堆相等的情况，例如x、x、y、y、z、z.6堆的情况。在这种情况下先取的必输，很简单，先取的那人怎么取后取的那人就怎么取(如果对方把石头分配到一堆上，你就分配到与之对应的堆上)，总之保持这个相等的均势不变，这样到最后，后取的人就将取走最后一堆石头。
知道这个结论后，就可以把N堆中两两相等的堆去掉，来讨论互不相等的堆来。
（1）只有一堆x，第一个人直接全部取走就胜利了。(显然x、y、y的情况也是第一人胜，所以忽略相等的石头)；
（2）x、y的形式(这里不妨假设递增，下同)。第一人从第二堆中取走(y-x)个石头，这样两堆相等，最终还是第一人胜；
（3）x、y、z的形式。第一人从最后一堆中取走(z+x-y)个石头，再将(y-x)个石头移到第一堆上(z>y-x一定成立)，这样还是第一人胜。
依此类推，移动个数最多的石头堆然后再分配总可以前面变成两两相等的情况。可见只要开始不全是两两相等，那先取者必胜。