2016-09-13から1日間の記事一覧
問題 問題概要 省略 解法 dpで解いた。dp[i][j] := i番目のアトラクションまで見て、待ち時間の総和がjの時の満足度の最大値、をループで回して埋めていった。やり方は、個数制限なしナップザック問題を解くイメージ。実装方法はcntでi番目のアトラクション…
問題 問題概要 省略 解法 2次元座標のなかで、スタートからゴールまで最短距離で行けるかを判定する問題。最短経路を求めるのだから、bfsで解けばいい。ただし、よくある迷路のような問題で最短距離を求める問題は、状態が座標のみでよいが、今回は残りの体…
問題 問題概要 省略 解法 スタートからゴールにたどりつく方法が、スタートからゴールまでオアシスを使わずに行くか、オアシスを利用して、ゴールに行くかの2通りである。まず、スタートからゴールまでオアシスを使わずに、ゴールに行けるかを調べる。調べ方…