3535298_ac_219ms_3552k.java

来自「北大大牛代码 1240道题的原代码 超级权威」· Java 代码 · 共 52 行

import java.util.*;

public class Main {
	private Scanner in;
	private long [][] upd;

	public static void main(String [] args) {
		new Main().run();
	}

	private void init() {
		upd = new long [232][];

		for (int i = 1; i < 232; i++) {
			upd[i] = new long [i + 1];
			upd[i][0] = upd[i][i] = 1;
		}
		for (int i = 2; i < 232; i++) {   
			for (int j = 1; j < i; j++) {   
				if (i - j * 2 < 0) {
					upd[i][j] = 0;
				} else {
					if (i - j * 2 == 0) {
						upd[i][j] = 1;
					} else {
						int tmp = i - j * 2;
						upd[i][j] = 0;
						for (int k = j; k <= tmp; k++) {
							upd[i][j] += upd[tmp][k];
						}
					}
				}
				upd[i][0] += upd[i][j];
			}
			upd[i][i] = 1;
		}
	}

	private void run() {
		init();
		int n;
		in = new Scanner (System.in);

		while (true) {
			n = in.nextInt();
			if (n == 0) {
				break;
			}
			System.out.println(n + " " + upd[n][0]);
		}
	}
}