fc2ブログ



錬金マスター

2009.09.07 22:37  パソコン甲子園 2009

パソコン甲子園2009予選 問題07 錬金マスター

問題はこちら

レシピの連鎖にサイクルが無いので、再帰で最小コストを求めることができます。

問題の仕様は残念ながら簡単化されていて(難易度調整のためでしょう)、サイズが小さく、作るものも1つ、1つのアイテムを作るレシピはたかだか1つしかないので、メモする(動的計画法にする)必要もないようです。

以下のプログラムは1つのアイテムが複数のレシピを持てるようにしてあります。

名前、値段、レシピのリストを持つ Item クラスを作ります。
getCost( stirng name ) で名前が nameである アイテム item を作る最小のコストを求めます。
最小のコストは以下のうち小さい方になります:
  • item のコスト
  • item を作るレシピの中でコストが最小のものであるコスト

この問題の仕様ではレシピが1つしかないので、以下のうち小さい方を選べばよい:
  • item のコスト
  • item をレシピで作る(ある場合は)コスト


スポンサーサイト



テーマ : プログラミング - ジャンル : コンピュータ

| コメント(0) | トラックバック(0) | ↑ページトップ |

この記事へのコメント

コメントを書く


管理人にのみ表示

↑ページトップ

この記事へのトラックバック

この記事にトラックバックする(FC2ブログユーザー)

↑ページトップ