AOJ-1167: ポロック予想 (Pollock's conjecture)

AOJ ICPC

keyword

動的計画法　Java

問題概要

整数N(<10^6)が与えられる。n*(n+1)*(n+2)/6で表される数を正四面体数と言うが，Nが最小いくつの正四面体数で表されるか求める問題。

解法

前からDPで計算量O(N^(4/3))程度。メモ化再帰だと書き方によってはスタックオーバーフローするかもしれない。

感想

ソースコード失くしたので書き直した。

import java.util.Arrays;
import java.util.Scanner;

public class Main{

	final int MAX_N = 1000002;
	int[] dp1 = new int[MAX_N], dp2 = new int[MAX_N];

	void run(){
		Scanner in = new Scanner(System.in);
		Arrays.fill(dp1, Integer.MAX_VALUE);
		Arrays.fill(dp2, Integer.MAX_VALUE);
		dp1[0] = dp2[0] = 0;
		for(int i=0; i<MAX_N; i++){
			for(int j=1, sum=1; i + sum < MAX_N; j++, sum += j*(j+1)/2){
				dp1[i+sum] = Math.min(dp1[i+sum], dp1[i]+1);
				if((sum&1)>0){
					dp2[i+sum] = Math.min(dp2[i+sum], dp2[i]+1);
				}
			}
		}
		for(int n = in.nextInt(); n > 0; n = in.nextInt()){
			System.out.println(dp1[n] + " " + dp2[n]);
		}
	}

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