Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

LiveArchive 4857 - Halloween Costumes (この記事を編集する[管理者用])

Source

ACM/ICPC Asia - Dhaka (Bangladesh) - 2010/2011
UVa: Dhaka Regional Semilive (2010-11-06) (blog)
LiveArchive 4857

問題概要

何枚でも重ねて着ることはできるが,一度脱いだコスチュームをまた着ることはできない.
順番に,いちばん外側に来ている状態にしたい出したいコスチュームの番号が与えられたとき,最小で何着コスチュームが必要かを求める問題.
与えられる番号の数列の要素は100要素以下.

解法

DP.
状態は考える範囲と,その範囲のすぐ外で一番外側に来ているコスチュームの番号.
一見状態数がO(n^3)に見えるが実質O(n^2)しか考える必要がなく,合計の計算量もO(n^3)になる.

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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