Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

UVa 12030 - Help the Winners (この記事を編集する[管理者用])

Source

Modified National Programming Contest of Bangladesh (2011-06-19)
UVa 12030

問題概要

N個ずつ,服と靴があって,それぞれの相性が3段階で与えられる.(0=ダメ・1=普通・2=良い のどれか)
服と靴を組み合わせて,N個のペアを作るとき,以下の条件の少なくても一方を満たす物の数を求める問題.
 1. すべての組み合わせが普通以上
 2. 少なくても1つは良い組み合わせになっている

解法

DP.
各部分セットに対して,
 少なくても1つは良い組み合わせ
 良い組み合わせがなくて,ダメな組み合わせがある
 すべて普通の組み合わせ
のパターン数をメモする.

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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