Codeforces Round #277.5(Div.2) E. Hiking(2부 DP)

제목: LINK
한 사람이 0곳에서 출발하면 모두 n개의 휴식처가 있고 각 지역은 0의 거리 x[i]와picturesqueness b[i]가 있다. 도착할 거리 >=x[n],(마지막 n-th 필수), 중간의 휴식점을 선택할 수 있어sigma(sqrt(x[j]-x[i]-l))/sigma(b[j])가 가능한 한 작아진다.j는 현재 휴식점, i는 이전 휴식점이다.2점짜리 문제에서 요구한 결과를 2점짜리 값마다 검증할 수 있다(DP할 수 있다)
약간 01점 짜는 맛이야.

import java.util.*; 
public class Main {	
	public static void main(String argsp[]) {
		Sol x = new Sol(); 
		x.sol(); 
	}
}
class Sol{
	static int N = 1111; 
	int n, m ; 
	int x[] = new int[N]; 
	int b[] = new int[N];
	double dp[] = new double[N];
	int pre[] = new int[1111]; 
	boolean test(double in) {
		dp[0] = 0; 
		for(int i = 1;i <= n; i++) {
			dp[i] = -1e10; 
			for(int j = 0; j < i; j++) {
				double tmp = dp[j] + in * b[i] - Math.sqrt(Math.abs(x[i] - x[j] - m)); 
				if(tmp > dp[i]) {
					dp[i] = tmp;
					pre[i] = j; 
				}
			}
		}
		return dp[n] >= 0; 
	}
	void sol() {
		Scanner cin = new Scanner(System.in);
		n = cin.nextInt(); 
		m = cin.nextInt(); 
		for(int i = 1;i <= n; i++) {
			x[i] = cin.nextInt(); 
			b[i] = cin.nextInt(); 
		}
		double l = 0, r = 1e10; 
		for(int i = 0; i <= 100; i++) {
			double mid = (l+r) / 2; 
			if(test(mid)) r = mid; 
			else l = mid; 
		}
		List L = new ArrayList(); 
		L.clear(); 
		for(int t = n; t != 0; t = pre[t])  L.add(t);
		for(int i = L.size() - 1; i >= 0; i--) {
			System.out.println((int)L.get(i) ); 
		}
	}
}