UVa 12840 - The Archery Puzzle

Source

Second UVa regional warmup(20141101)
UVa 12840

問題概要

アーチェリーで的は $N$ 個の部分にわけられていて,部分 $k$ を射ると $P_k$ 点もらえる.
今,合計で $S$ 点獲得したことがわかっている.
何本目にどの点数を得たかを求める問題.
答えが存在しないならそれを指摘し,複数存在するならば,矢を打った回数ができるだけ少ないものの中で,更に $1$ 本目の点数が最も高いものの中で,$2$ 本目の点数が最も高いもの,…,というものを出力する.

解法

DP+経路復元.
状態を(打った本数,合計点)とし,それが達成可能かどうかを計算していく.
点数は $S$ 点まで,また,打った本数は $S$ を超えないので,そこまで求めれば良い.
時間計算量は $O(TNS^2)$ 程度だが,答えが見つかったらそれ以上計算しないとかすれば余裕で間に合う.

C++によるスパゲッティなソースコード

この部分を表示するには表示権限を持つユーザーでログインする必要があります.


Current time: 2017年09月22日22時17分00秒
Last modified: 2014年11月08日19時22分22秒 (by laycrs)
Tags: Competitive_Programming UVa_Online_Judge UVa_Contest_20141101_1
トップページに戻る

Logged in as: unknown user (not login)

ログイン: