Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

LiveArchive 4510 - Slalom (この記事を編集する[管理者用])

Source

Europe - Southwestern - 2009/2010
SWERC 2009 (One more ICPC Regional Contest, 2009-11-07)
LiveArchive 4510

問題概要

初期地点と,x軸に平行な線分がn個与えられる.(nは1000以下)
初期地点は,もっともy座標の値が大きい.
初期地点から,その線分を全て通るような経路のうち,長さ最小のものの長さを求める問題.

解法

それぞれの線分の端点に移動するのに必要な長さをDPで計算する.
上手く計算しないと,O(n^3)になっちゃうけど,点を角度でソートしたりして,O(n^2 log n)ぐらいで書いた.
ACもらえるけど,遅いので,もっと良い方法があるのかもしれない.

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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