Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

Aizu 2156 - Magic Slayer (この記事を編集する[管理者用])

Source

ICPC OB/OGの会 2009 夏合宿 2日目
Aizu 2156

問題概要

N匹のモンスターのHPが与えられる.
魔法がM種類あって,単体魔法か全体魔法か,消費MPと与えるダメージが与えられる.
モンスターを全滅させるのに必要な最小MPを求める問題.
NとMは100以下.HPは100000以下.

解法

単体魔法,全体魔法で,それぞれ,あるダメージ以上を与える最小MPをDPで最初に計算する.
後は,全体魔法でいくらのダメージを与えて,残りのモンスターを倒すか,全探索して,必要最小MPを求める.
O(N+M+HPの最大値)ぐらい.

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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