取石子游戏不同玩法的解决方案

玩法一（1堆n个石子每次最多取m个）
显然，如果n=m+1，那么由于一次最多只能取m个，所以，无论先取者拿走多少个，后取者都能够一次拿走剩余的物品，后者取胜。因此我们发现了如何取胜的法则：如果n=（m+1）r+s，（r为任意自然数，s≤m),那么先取者要拿走s个物品，如果后取者拿走k（≤m)个，那么先取者再拿走m+1-k个，结果剩下（m+1）（r-1）个，以后保持这样的取法，那么先取者肯定获胜。总之，要保持给对手留下（m+1）的倍数，就能最后获胜。

import java.util.*;
import java.io.*;

class Main{

    static StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
    static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
    static int nextInt()throws Exception{
        in.nextToken();
        return (int)in.nval;
    }

    static Integer[] a;
    static boolean[] st;
    static int length, n, sum;
     static void swap(int i,int j)
    {
        int tmp = a[i];
        a[i] = a[j];
        a[j] = tmp;
    }
    static void reverse()
    {
        int i = 0;
        int j = n - 1;
        while(i <= j) 
        {
            swap(i,j);
            i ++;
            j --;
        }
    }
    public static boolean DFS(int c, int cur, int start){
        if(c*length==sum) return true;
        if(cur==length) return DFS(c+1, 0, 0);
        if(cur>length) return false;
        for(int i=start; i<n; i++){
            if(st[i]) continue;
            st[i] = true;
            if(DFS(c, cur+a[i], i+1)) return true;
            st[i] = false;
            if(cur==0) return false;
            if(cur+a[i]==length) return false;
            while(i<n-1&&a[i]==a[i+1]) i++;
        }
        return false;
    }

    public static void main(String[] args) throws Exception{
        n = nextInt();
        while(n!=0){
            a = new Integer[n];
            st = new boolean[n];
            length = sum = 0;

            for(int i=0; i<n; i++){
                a[i] = nextInt();
                length = Math.max(length, a[i]);
                sum += a[i];
            }
            Arrays.sort(a);//这里用Arrays.sort(a,(o1, o2)->o2-o1;就会超时
            reverse();
            while(length<=sum){
                if(sum%length==0&&DFS(0, 0, 0)) break;
                length++;
            }
            out.println(length);
            n = nextInt();
        }
        out.close();
    }
}