Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

UVa 11793 - Electoral Districts (この記事を編集する[管理者用])

Source

VIII Programming Olympiads in Murcia (2010-05-15) (blog)
UVa 11793

問題概要

N*Nのグリッドがある.N=3,4,5のどれか.
それぞれの地域で,政党Aに投票する人数と,政党Bに投票する人数がわかっている.
N*Nのグリッドを連結なサイズNのN個の選挙区に分ける.
 政党Aが勝てる選挙区の数 - 政党Bが勝てる選挙区の数
の最大値を求める問題.

解法

連結であることの制約が結構厳しくて,状態数は実際は少ないのでDPする.
状態の依存関係を表すグラフは最初に作っておいて,使いまわすと良い.

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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