AOJ-1306: Balloon Collecting

keyword

動的計画法　Java

問題概要

風船がN(<40)個落ちてくる。それぞれ落ちる位置x(<100)と時刻t(<50000)が与えられる。乗り物で風船を拾う。乗り物は最大で3つまで風船を積むことができて、x=0の位置で風船をリリースすることができる。乗り物は1単位距離移動するのに、(今搭載している風船の個数+1)単位時間かかる。全ての風船を拾ってリリースするまでに必要な総移動距離の最小値を求める問題。無理なときは幾つ目の風船が拾えないか答える。

解法

見た瞬間にDP。多分一番楽なのは状態をdp[i番目の風船][搭載している風船の個数]とする。計算量O(N)。dp[座標][時間][風船の個数]とやっても解けるかもしれない。意味ないけど。実装時間17分。

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

public class Main{

	int N;
	int[] ps;
	int[] ts;

	void run(){
		Scanner in = new Scanner(System.in);
		for(;;){
			N = in.nextInt();
			if(N==0) return ;
			ps = new int[N];
			ts = new int[N];
			for(int i=0; i<N; i++){
				ps[i] = in.nextInt();
				ts[i] = in.nextInt();
			}
			int ans = solve();
			if(ans > 0) System.out.println("OK " + ans);
			else System.out.println("NG " + (-ans));
		}
	}

	int solve(){
		int[][] dp = new int[N][3];
		for(int i=0; i<N; i++){
			Arrays.fill(dp[i], Integer.MAX_VALUE);
		}
		if(ts[0] < ps[0]) return -1;
		dp[0][0] = ps[0];
		for(int i=0; i<N-1; i++){
			for(int j=0; j<3; j++)if(dp[i][j] < Integer.MAX_VALUE){
				if(ts[i] + (j+2)*ps[i] + ps[i+1] <= ts[i+1]){
					dp[i+1][0] = Math.min(dp[i+1][0], dp[i][j] + ps[i] + ps[i+1]);
				}
				if(j<2 && ts[i] + (j+2)*Math.abs(ps[i]-ps[i+1]) <= ts[i+1]){
					dp[i+1][j+1] = Math.min(dp[i+1][j+1], dp[i][j] + Math.abs(ps[i] - ps[i+1]));
				}
			}
			boolean ok = false;
			for(int j=0; j<3; j++){
				if(dp[i+1][j] < Integer.MAX_VALUE){
					ok = true;
				}
			}
			if(!ok){
				return -(i+2);
			}
		}
		int ans = Integer.MAX_VALUE;
		for(int j=0; j<3; j++){
			ans = Math.min(ans, dp[N-1][j]);
		}
		return ans + ps[N-1];
	}

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