Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

UVa 12325 - Zombie's Treasure Chest (この記事を編集する[管理者用])

Source

Asia Shanghai Regional Semilive hosted by Fudan University (2011-10-23)
UVa 12325

問題概要

容量Nの箱がある.
宝石1が無限にあって,1個あたり容量S1を消費し,V1の価値がある.
宝石2が無限にあって,1個あたり容量S2を消費し,V2の価値がある.
詰めれる価値の最大値を求める問題.
N, V1, V2, S1, S2はすべて2^31未満.

解法

単位容量あたりの価値(V/S)が小さい方は,たかだか容量LCM(S1,S2)未満しか詰め込まれない.
何故なら,容量換算でLCM(S1,S2)だけ減らして,もう一方のを詰めればいいから.
なので,LCM(S1,S2)切らない程度に,単位容量あたりの価値が大きい方をとりあえず詰めてしまう.
後は,残りの部分に,容量が大きい方を何個入れるかで全探索する.
計算量はちゃんと見積もってないけど,きっとO(sqrt(2^31))程度.
答えは,32bit整数に収まらないことに注意.

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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