Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

LiveArchive 4812 - Hyperactive Girl (この記事を編集する[管理者用])

Source

ACM/ICPC Latin America - South America - 2010/2011
UVa: ACM ICPC Latin America Regional Contest (2010-10-24) (blog)
LiveArchive 4812
SPOJ 7759 [MHLAR10] (2010-11-07 20:16追加)

問題概要

[s,t]という形の区間が100個以下与えられる.
[0,M]を埋め尽くすような区間の極小集合の数をmod 10^8で求める問題.
埋め尽くすというのは,0以上M以下の点は選んだ区間のどれか少なくても1個に属している.
極小というのは,選ばれた区間のうち,どの1つを取り除いても,埋め尽くすという条件を満たさなくなること.

解法

終了時間でソートしてあげて,前に使った区間と2個前に使った区間を状態としてDPする.

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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