Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

UVa 11903 - e-Friends (この記事を編集する[管理者用])

Source

A National Bangladeshi Contest (2011-01-09) (blog)
UVa 11903

問題概要

N人 (12以下) の人を以下の条件をみたすように一列に並べる方法の数を求める問題.
N人の人はそれぞれ嫌っている相手のリストが与えられて,自分の1つ前に嫌っている人がいるなら不快度がK (0以上10^6以下) だけ増す.
クエリが1000個以下与えられて,合計不快度がG以下 (0以上10^8以下) になるような並べ方の総数を求める.

解法

結局は何人まで不快でも良いかという条件になる.(K=0の時に注意)
最後に並んだ人,すでに並んだ人の集合を状態として,不快な人の数が何人の時のこれ以降の並び方の総数を記憶する形のDPをする.

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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