AOJ 1306 ICPC Asia resional 2010 Problem B: Balloon Collecting

問題

空から風船が落ちてくるので、それを台車で回収したい。
それぞれの風船は、時間t[i]にx座標x[i]の地点に落ちる。
このとき台車はちょうどx[i]の位置にいる必要がある。

台車は回収した風船を、x座標が0の地点の小屋に入れることができる。
台車には風船が3つまで乗り、風船がk個乗っているときに単位距離を移動するのにかかる時間はk+1である。

台車は時刻0のとき小屋にいる。
台車は風船を全て回収できるか、できるならそのときの移動距離の最小値を、
そうでないなら最初に回収できなくなる風船の番号を答えよ。

制約条件

n≦40
x[i]≦100
t[i]≦50000

方針

風船をi個回収したときの、位置x[j]にいて現在台車に乗っている風船がk個のときの移動の最小距離をdp[i][j][k]とする。

これを風船ごとに、一度小屋に寄ってからその風船を取るか、
直接風船を取るかを選ぶように更新していくdpをすればいい。

ソースコード

int n,X[100],t[100];
int dp[100][4];

int main()
{
	while(cin>>n,n){
		rep(i,n)cin>>X[i+1]>>t[i+1];
		
		rep(i,n+1)rep(k,4)dp[i][k]=1e9;
		dp[0][0]=0;
		
		rep(i,n)rep(k,4){
			if(k<3&&abs(X[i+1]-X[i])*(k+1)<=t[i+1]-t[i])
			dp[i+1][k+1]=min(dp[i+1][k+1],dp[i][k]+abs(X[i+1]-X[i]));
			if(X[i]*(k+1)+X[i+1]<=t[i+1]-t[i])
			dp[i+1][1]=min(dp[i+1][1],dp[i][k]+X[i]+X[i+1]);
		}
		int ans=1e9,mx;
		rep(k,4)ans=min(ans,dp[n][k]+X[n]);
		if(ans>=1e9){
			rep(i,n)rep(k,4)if(dp[i][k]<1e9)mx=i;
			cout<<"NG "<<mx+1<<endl;
			continue;
		}
		cout<<"OK "<<ans<<endl;
	}
	return 0;
}