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; }