Entries

スポンサーサイト (この記事を編集する[管理者用])

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/793-f66b15f7
この記事にトラックバックする(FC2ブログユーザー)

LiveArchive 4613 - Mountain Road (この記事を編集する[管理者用])

Source

ACM/ICPC Europe - Northwestern - 2009/2010
Another Regional Contest (NWERC 2009, 2009-11-14) (blog)
LiveArchive 4613
PKU 3846 [問題名: Pirvate problem 20100801 E] (2010-10-02 09:45追加)

問題概要

細い道がある.
左右から同時に車が進入するとぶつかるので,片方ずつしか進めない.
しかし,片方から2台進むときは,道の最中のどの点においても,10秒以上の間隔を空けなければいけない.
左右どちらに,時刻いつ辿り着いて,その車の最大スピードで道を進んだ場合の必要時間が与えられるので,全ての車が道を超えるまでの最小所要時間を求める問題.
車の数は200以下.

解法

どちら向きの車を走らせるかが決まっているなら,到着順に,出発できるならすぐ出発するのが最適.
最後にどちら側の車が通ったか,右側からきている車は後何台残っているか,左側は後何台か,を状態にDPする.
領域量O(n^2),計算量O(n^3).

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/793-f66b15f7
この記事にトラックバックする(FC2ブログユーザー)

Appendix

Recent Articles

ブログ内検索

Ads


(プライバシーポリシー)
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。