2336 Ferry Loading II

問題概要

n台の車を同時につめるフェリーがある。
川の向こう岸に行く、または戻るのにかかる時間はtである。


川にm台の車がやってくるのでそれらを全て向こう岸へ渡したい。
それぞれの車が来る時間が与えられるので、全ての車を向こう岸へ渡すのにかかる時間の最小値および、往復回数を最小にする場合の往復回数を求めよ。

n,t,m<1440を満たす。

解法

フェリーが往復する回数の最小値は単に割り算すればよい。


最速の時間は、
dp[i]にi台の車を向こう岸へ運ぶのにかかる最短の時間とすると、
n個までの車を一遍に積めるので、k台車を同時に積むとき
dp[i]=min(dp[i-k]|1≦k≦n)+tとi番目の車が来るまでの時間の大きいほうという漸化式でDPすればよい。

ソースコード

int T,n,t,m,c[1440];
int dp[1441];

int main(){
	scanf("%d",&T);
	rep(U,T){
		scanf("%d%d%d",&n,&t,&m);
		rep(i,m)scanf("%d",c+i);
		dp[0]=-t;
		for(int i=1;i<=m;i++){
			dp[i]=1<<30;
			rep(j,min(i,n))dp[i]=min(dp[i],max(dp[i-j-1]+t,c[i-1])+t);
		}
		printf("%d %d\n",dp[m],m/n+(m%n!=0));
	}
	return 0;
}