POJ 2355 Railway tickets

見るからにDPっぽいDP.

N <= 10^5なのでO(N^2)では厳しそう。
だから恐らくO(N)なんだけど頭が悪いからO(N log N)でといた。

dp[i] := i番目の駅に行くときのかかる値段の最小値

で求まる。

よく読んでいなくて無駄なWAを生やしすぎたし英語力ない。

ACしたあと中国人のブログ見てたらみんなO(N)でといてるし頭悪いなーと実感。

#include <algorithm>
#include <cstdio>

using namespace std;
int d[10007];
int dp[10007];
int main(){

	int l[5],c[5],a,b,n;
	scanf("%d%d%d%d%d%d%d%d%d",&l[0],&l[1],&l[2],&c[0],&c[1],&c[2],&n,&a,&b);
	a--;b--;
	if(a > b)swap(a,b);
	for(int i = 1;i < n;i++){
		scanf("%d",&d[i]);
	}
	dp[a+1] = 1000000000;
	for(int i = 0;i < 3;i++){
		if(d[a+1]-d[a] <= l[i])dp[a+1] = min(dp[a+1],c[i]);
	}

	for(int i = a+2;i <= b;i++){
		dp[i] = dp[i-1] + c[2];
		for(int j = 0;j < 3;j++){
			int lb = -1,ub = i;
			while(ub - lb > 1){
				int mid = (ub+lb)/2;
				if(d[i]-d[mid] <= l[j])ub = mid;
				else lb = mid;
			}
			if(i == ub)continue;
			dp[i] = min(dp[i],dp[ub]+c[j]);
		}
	}
	printf("%d\n",dp[b]);
	return 0;
}