Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

LiveArchive 4712 - Airplane Parking (この記事を編集する[管理者用])

Source

ACM/ICPC Asia - Phuket, Vietnam - 2009/2010
LiveArchive 4712
SPOJ 7387 [PKA] (2010-09-28 13:20追加)

問題概要

飛行機の駐車場.
飛行機300機以下の着陸時間,離陸時間が与えられる.離陸時間の方が厳密に後.
先に着陸した飛行機ほど,後に離陸しなければいけない.
全く同じ時間に行動する飛行機同士は,どちらを先に動かしても良い.
最高で,何機の飛行機をこの駐車場で処理出来るかを求める問題.

解法

時間座標を圧縮してDPした.
状態は時間[st,ed]を使って処理出来る飛行機の数.
着陸時間A,離陸時間Bの飛行機を使う場合,dp[st,ed] = 1+dp[A,B]+dp[B,ed] (+dp[A,st])など.
ただし,全く同じ時間にアクションを起こす飛行機はどれを先にやっても良いことに注意する.

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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