PKU 2336 Ferry Loading II
http://poj.org/problem?id=2336
船で川の向こうに車を運ぶことを考える。
運ぶ車はn台、船で一度に運べる車の最大数はm台、船が川の端から端まで行くのにt時間かかる(往復2*t時間)。
車の来る時間帯がわかっている時、最後の車を運び終わるのに必要な最小の時間と、その時間で終わるときの最小の往復回数を答えろというような問題。
DP。
微妙にてこずりました。
PI dp[2000]; int in[2000]; void solve(){ int n,t,m; cin>>m>>t>>n; rep(i,n)cin>>in[i]; dp[0]=mp(0,0); rep(i,n){ PI tmp=*min_element(dp+max(0,i+1-m),dp+i+1); dp[i+1].F=max(tmp.F,in[i])+2*t; dp[i+1].S=tmp.S+1; } cout<<dp[n].F-t<<' '<<dp[n].S<<endl; } main(){ int T; cin>>T; while(T--)solve(); }