[置頂] 九度筆記之 1494：Dota

題目1494：Dota

1 秒

記憶體限制：128 兆

特殊判題：否

送出：559

解決：122

題目描述：

大家都知道在dota遊戲中，裝備是對于英雄來說十分重要的要素。

英雄們不僅可以購買單個的裝備，甚至某些特定的裝備組合能夠合成更強的裝備。

為了簡化問題，我們将每個裝備對于英雄的功能抽象為一個整數：價值。同時，如上所說，一些特定的裝備可以用來合成更強的裝備，玩家會是以獲得除原裝備價值外額外的價值。

給定玩家現有的金錢數，每個裝備的價格和其對應的價值，以及裝備合成的資訊。輸出，其能獲得的最大價值數。

注意：每件裝備隻能參與合成一件合成裝備（即原裝備參與合成後得到合成後的新裝備，原裝備消失），除非一次購買多個該種裝備。

輸入：

輸入包含多組測試資料，每組測試資料第一行為三個整數n，m，g(1<=n<=100),(0<=m<=100),(1<=g<=1000)。

分别表示存在的裝備總數n，存在的裝備合成關系數m，和英雄所有的金錢g。

接下去n行，每行兩個整數（p，v）（1<=p<=100,1<=v<=100）分别表示該件裝備的價格p，和其自身的價值v。

每組測試資料的最後為m行資料，每行由兩部分組成。開頭一個整數t(1<=t<=n)，表示該組合成關系中需要t件裝備，下去緊跟t件裝備編号（按照裝備在輸入中的順序從1到n編号），表示參與合成該裝備的裝備編号，最後一個數s（1<=s<=1000），代表這t件物品合成道具後獲得的額外價值。

輸出：

對于每組測試資料，輸出一個整數，代表英雄可以獲得的最大價值。

樣例輸入：

3 1 100
100 20
50 9
50 9
2 2 3 1
3 1 100
100 20
50 9
50 9
2 2 3 3      

樣例輸出：

20
21      

算法分析

     這道題主要的屬于背包問題，用動态規劃解決，需要注意的是兩點。

     1. 我們把合成的裝備看作單獨的一件裝備，計算合成裝備的價格（合成所需裝備價格之和），合成裝備的價值（合成所需裝備價值之和 加上 額外價值）。

for(int i = num_weapons;i<num_weapons+num_merge;i++){
        int t=0;
        std::cin>>t;
        price[i]=0;
        value[i]=0;
        for(int j = 0;j<t;j++){
            int id_weapon;
            std::cin>>id_weapon;
            price[i]+=price[id_weapon-1];
            value[i]+=value[id_weapon-1];
        }
        int s = 0;
        std::cin>>s;
        value[i]+=s;
    }      

     2.這道題和其它背包問題不同的在于 裝備的數量并不是固定的，玩家可以重複購買多個同一種裝備，包括合成裝備，隻要錢夠就行。是以在動态規劃更新dp的時候，就是從低到高更新。

for(int j = price[i];j<gold+1;j++){
            maxvalue[j] = std::max(maxvalue[j],maxvalue[j-price[i]]+value[i]);
        }      

源程式

//============================================================================
// Name        : judo1494.cpp
// Author      : 
// Version     :
// Copyright   : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================
//02988825547
#include <iostream>
#include <cmath>
using namespace std;
void dota(int num_weapons,int num_merge,int gold){
    int *price = new int[num_weapons+num_merge];
    int *value = new int[num_weapons+num_merge];
    int *maxvalue = new int[gold+1];
    for(int i = 0;i<num_weapons;i++){
        std::cin>>price[i]>>value[i];
    }
    for(int i = num_weapons;i<num_weapons+num_merge;i++){
        int t=0;
        std::cin>>t;
        price[i]=0;
        value[i]=0;
        for(int j = 0;j<t;j++){
            int id_weapon;
            std::cin>>id_weapon;
            price[i]+=price[id_weapon-1];
            value[i]+=value[id_weapon-1];
        }
        int s = 0;
        std::cin>>s;
        value[i]+=s;
    }

    for(int i = 0;i<gold+1;i++){
        maxvalue[i]=0;
    }
    for(int i = 0;i<num_weapons+num_merge;i++){
        for(int j = price[i];j<gold+1;j++){
            maxvalue[j] = std::max(maxvalue[j],maxvalue[j-price[i]]+value[i]);
        }
    }
    std::cout<< maxvalue[gold]<<std::endl;
    delete []price;
    delete []value;
    delete []maxvalue;

}
int main() {
    //cout << "!!!Hello World!!!" << endl; // prints !!!Hello World!!!
    int n;
    int m;
    int g;
    while(std::cin>>n>>m>>g){
        dota(n,m,g);
    }
    return 0;
}

/**************************************************************
    Problem: 1494
    User: KES
    Language: C++
    Result: Accepted
    Time:30 ms
    Memory:1520 kb
****************************************************************/