Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

UVa 12346 - Water Gate Management (この記事を編集する[管理者用])

Source

ACM-ICPC Asia Phuket Regional Semilive (2011-11-06)
UVa 12346

問題概要

蛇口がn個 (20以下) ある.
i番目の蛇口を買い取れば,1時間あたりG[i]の水が得られる.買うのには最初にC[i]のコストが掛かり,時間あたりのコストは掛からない.
m個 (50以下) のクエリに答える問題で,各クエリは,今から何時間以内に,ある量以上の水が欲しいとき,最小コストを求める.

解法

2^nパターン全部試す.
一応最初に,各パターンについて,コストと,1時間あたりに得られる水の量は先に計算しておいた.
クエリが多くなると,2^nパターンを得られる水の量・コスト順にソートしておいて,考える必要のないパターンを省き,クエリごとに二分探索,だと思うけど,クエリの数が小さいので必要ない.

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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