990 Diving for gold

990 - Diving for Gold

Solution:

 #include  
    #include < stdio.h >
    using namespace std;
    #define INF - 1
    #define max_teasure 30 + 5
    int TOTAL_AIR, W, NUM_OF_TEASURE, MAX_GOLD_FOUND;
    int parentPath[max_teasure];
    int parentIndex[max_teasure];
    int DP[max_teasure][max_teasure];
    int calculateMaxGold(int level, int max_gold, int remaining_air);
    void init();
    int taken = 0;
    struct Teasure {
        int distance;
        int numberOfGold;
        int totalCostPerDriving;
    }
    teasure[max_teasure];
    int main() {
        freopen("990.txt", "r", stdin);
        TOTAL_AIR = W = NUM_OF_TEASURE = 0;
        while (cin >> TOTAL_AIR >> W) {
            cin >> NUM_OF_TEASURE;
            for (int i = 0; i < NUM_OF_TEASURE; i++) {
                cin >> teasure[i].distance >> teasure[i].numberOfGold;
                teasure[i].totalCostPerDriving = 3 * W * teasure[i].distance;
            }
            init();
            MAX_GOLD_FOUND = -1;
            MAX_GOLD_FOUND = calculateMaxGold(0, 0, TOTAL_AIR);
            cout << MAX_GOLD_FOUND << endl;
            int count = 0;
            for (int i = 0; i < max_teasure; i++) {
                if (parentPath[i] == 1) {
                    parentIndex[count++] = i;
                }
            }
            cout << count << endl;
            for (int i = 0; i < count; i++) {
                cout << teasure[parentIndex[i]].distance << " " << teasure[parentIndex[i]].numberOfGold << endl;
            }
            cout << endl;
            TOTAL_AIR = W = NUM_OF_TEASURE = 0;
        }
        return 0;
    }
    int calculateMaxGold(int level, int max_gold, int remaining_air) {
        if (DP[level][remaining_air] != INF) return DP[level][remaining_air];
        if (level == NUM_OF_TEASURE) {
            return max_gold;
        }
        int notTaken = 0, taken = 0;
        notTaken = calculateMaxGold(level + 1, max_gold, remaining_air);
        if ((remaining_air - teasure[level].totalCostPerDriving) >= 0) {
            taken = calculateMaxGold(level + 1, max_gold + teasure[level].numberOfGold, remaining_air - teasure[level].totalCostPerDriving);
        }
        if (taken > notTaken) {
            parentPath[level] = 1;
            DP[level][remaining_air] = taken;
        } else {
            parentPath[level] = 0;
            DP[level][remaining_air] = notTaken;
        }
        return DP[level][remaining_air];
        //return (taken>notTaken?taken:notTaken);
    }
    void init() {
        for (int i = 0; i < max_teasure; i++) {
            parentPath[i] = INF;
        }
        for (int i = 0; i < max_teasure; i++) {
            for (int j = 0; j < max_teasure; j++) {
                DP[i][j] = INF;
            }
        }
    }