Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

UVa 12002 - Happy Birthday (この記事を編集する[管理者用])

Source

World Finals Warmup II (2011-05-07) (blog)
UVa 12002

問題概要

一直線上のテーブルに皿がN個 (500以下) 置かれている.
皿の大きさが与えられる.
テーブルを1回左から右に移動する際に,
 (1) 皿を無視する
 (2) 今,皿を持ってなければ,その皿を持つ
 (3) テーブルの皿が,今持っている一番上の皿のサイズと同じか小さければ,今持っている一番上の皿の上に追加できる
 (4) テーブルの皿が,今持っている一番下の皿のサイズと同じか大きければ,今持っている一番下の皿の下に追加できる
ということができる.
最高で何個の皿を持つことができるかを求める問題.

解法

最初に取る皿は全探索する.
後は,その皿より大きい物と小さい物に分けて,それぞれLIS (最長部分列) を求める.
最初の皿と同じサイズの皿を,大きいとみなすか,小さいとみなすかは両方試して良い方を採用した.

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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