Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

UVa 12511 - Virus (この記事を編集する[管理者用])

Source

The 8th Hunan Collegiate Programming Contest Semilive (2012-10-14)
UVa 12511

問題概要

1000要素以下の整数の配列A, Bが与えられる.
各要素は1以上100000未満.
A, Bに共通する増加列の中で最小のものの長さを求める問題.

解法

数字を圧縮して,各数字に対して,各場所から右にある最近の場所を求めておく.
後は,最後に増加列として使ったAの場所,Bの場所を状態にDPする.
状態数は見た目O(1000^2)だけど,そんなに多くない気がする.

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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