Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

UVa 12551 - Shares (この記事を編集する[管理者用])

Source

An European Reginal contest to be decided, SWERC 2012 Online (2012-11-24)
UVa 12551

問題概要

N個 (500以下) のアイテムの種類がある.
P個 (50000以下) の商品のセットが売られている.各セット1個までしか買えない.
各セットはN種類のアイテムがいくつか含まれている,
各アイテムの今日の値段と,明日の値段が与えられる.
各セットの価格は,含まれるアイテムの価格の和.
各アイテムは明日各値段で売れる.
今C円 (2^30以下) もっていて,借金などはできないとして,1日で儲けられる最大額を求める問題.

解法

DPする.
買えないセットを除外し,各セットの値段と現在持ってるお金のGCDで全部割って状態数を削減すると間に合う.
という解説だった.エスパーゲー.

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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