Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2012-04-02SRM353, SRM354 (Practice)

SRM 353 PlatformJumper

|  SRM 353 PlatformJumper - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク -  SRM 353 PlatformJumper - hama_DU@TopCoderへの道

http://www.topcoder.com/stat?c=problem_statement&pm=7847

  • ある台からある台に飛び降り可能な時、元の台に戻ることはできないはず。
    • なので、状態として「今どこにいるか」だけ分かっていればよい
  • グラフにしてダイクストラ。
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Queue;

public class PlatformJumper {
	class P {
		int x, y, c;
		P(int _x, int _y, int _c) {
			x = _x;
			y = _y;
			c = _c;
		}
	}
	
	class State {
		int now;
		int coin;
		State(int n, int c) {
			now = n;
			coin = c;
		}
	}
	
	public int maxCoins(String[] pl, int v, int g) {
		int len = pl.length;
		P[] p = new P[len];
		for (int i = 0 ; i < len ; i++) {
			String[] data = pl[i].split(" ");
			int x = Integer.valueOf(data[0]);
			int y = Integer.valueOf(data[1]);
			int c = Integer.valueOf(data[2]);
			p[i] = new P(x, y, c);
		}
		
		boolean[][] graph = new boolean[len][len];
		for (int i = 0 ; i < len ; i++) {
			for (int j = 0 ; j < len ; j++) {
				if (i == j) {
					continue;
				}
				long dx = Math.abs(p[i].x - p[j].x);
				int dy = p[i].y - p[j].y;
				if (dy < 0) {
					continue;
				}
				if (dx * dx * g <= 2L * dy * v * v) {
					graph[i][j] = true;
				}
			}
		}
		
		int[] dp = new int[len];
		Queue<State> q = new PriorityQueue<State>(100000, new Comparator<State>(){
			public int compare(State arg0, State arg1) {
				return arg1.coin - arg0.coin;
			}
		});
		for (int i = 0 ; i < len ; i++) {
			q.add(new State(i, p[i].c));
			dp[i] = p[i].c;
		}
		while (q.size() >= 1) {
			State s = q.poll();
			for (int t = 0 ; t < len ; t++) {
				if (graph[s.now][t]) {
					int ton = t;
					int tocoin = s.coin + p[t].c;
					if (dp[ton] < tocoin) {
						dp[ton] = tocoin;
						q.add(new State(ton, tocoin));
					}
				}
			}
		}
		
		
		int ma = 0;
		for (int i = 0 ; i < len ; i++) {
			ma = Math.max(ma, dp[i]);
		}
		return ma;
	}
}