錬金マスター

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

問題はこちら。

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

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

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

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

• item のコスト
• item を作るレシピの中でコストが最小のものであるコスト

この問題の仕様ではレシピが１つしかないので、以下のうち小さい方を選べばよい：

• item のコスト
• item をレシピで作る（ある場合は）コスト

#include<iostream>
#include<string>
#include<map>
#include<vector>
using namespace std;

#define MAX 200

class Item{
    public:
    string name;
    int cost;
    vector<vector<string> > recipes;

    Item(){}
    Item( string name, int cost ): name(name), cost(cost){ recipes.clear(); }

    void addRecipe(vector<string> r ){ recipes.push_back(r);}
};

int n;
map<string, int> N_I;
Item items[MAX];

int getCost( string name ){
    Item item = items[ N_I[name] ];
    int cost = item.cost;

    for ( int i = 0; i < item.recipes.size(); i++ ){
        vector<string> recipe = item.recipes[i];
        int sum = 0;
        for ( int j = 0; j < recipe.size(); j++ ){
            sum += getCost( recipe[j] );
        }
        cost = min( cost, sum );
    }

    return cost;
}

main(){
    int q, cost, nr, k;
    string name, source;
    while( cin >> n && n){
        for ( int i = 0; i < n; i++ ){
            cin >> name >> cost;
            items[i] = Item(name, cost);
            N_I[name] = i;
        }
        cin >> nr;
        for ( int i = 0; i < nr; i++ ){
            cin >> name >> k;
            vector<string> recipe;
            for ( int j = 0; j < k; j++ ){
                cin >> source;
                recipe.push_back(source);
            }
            items[ N_I[name] ].addRecipe(recipe);
        }
        cin >> name;
        cout << getCost( name ) << endl;
    }
}