当前位置：首页 » Project Euler » 详细页

Investigating in how many ways objects of two different colours can be grouped 题号：181 难度： 70 中英对照

Having three black objects B and one white object W they can be grouped in 7 ways like this:

(BBBW)(B,BBW)(B,B,BW)(B,B,B,W) (B,BB,W)(BBB,W)(BB,BW)

In how many ways can sixty black objects B and forty white objects W be thus grouped?

Solution

定义有序二元组$(a,b)$的自增运算： $$(a,b)++\quad=\quad (a+1,b)\quad if\, a+1< A$$ $$(a,b)++\quad=\quad (0,b+1)\quad if\,a+1=A $$ 有序二元组需满足$a< A\, and\, b< B$。 有序二元组的加法运算同理。 定义有序二元组的值为$a+(A+1)\times b$，则任意一个合法二元组对应独一无二的值，且值小于$(A+1)\times (B+1)$。 利用动态规划思想，考虑间隔$add=(add_a,add_b)$，对于所有合法二元组$start=(start_a,start_b)$都需要更新$d[start+add]+=d[start]$。 枚举$add$、枚举$start$即可。 初始情况为无物品时的方案数，$d[(0,0)]=1$。

Code 


public final class p181 {
    public static void main(String[] args) {
        long start=System.nanoTime();
        String result = run();        
        long end=System.nanoTime();
        System.out.println(result);
        System.out.println( (end-start)/1000000 + "ms" );
    }

	static int maxIndex[]=new int[]{40,60};
	static int size;
	static long d[];
	public static String run(){
		size = 1;
		for (int m : maxIndex) {
			size *= m + 1;
		}
		d = new long[size];
		d[0] = 1;
		return ""+solve();
	}

	static public long solve() {
		int zero[] = new int[maxIndex.length];
		int add[] = new int[maxIndex.length];
		while (increment(add, zero)) {
			int start[] = new int[maxIndex.length];
			int end[] = new int[maxIndex.length];
			for (boolean ok = true; ok; ok = increment(start, add)) {
				for (int i = 0; i < maxIndex.length; i++) {
					end[i] = start[i] + add[i];
				}
				int start1 = encode(start);
				int end1 = encode(end);
				d[end1] += d[start1];
			}
		}
		return d[size - 1];
	}

	static public int encode(int[] start) {
		int result = 0;
		int digitValue = 1;
		for (int i = 0; i < maxIndex.length; i++) {
			result += digitValue * start[i];
			digitValue *= maxIndex[i] + 1;
		}
		return result;
	}

	/**
	 * @return false if increment overflows
	 */
	static public boolean increment(int[] index, int[] headRoom) {
		for (int i = 0; i < maxIndex.length; i++) {
			if (index[i] + headRoom[i] < maxIndex[i]) {
				index[i]++;
				return true; // increment accomplished
			}
			index[i] = 0; // zero and carry
		}
		return false;
	}
}
83735848679360680
64ms