九度 1494：Dota(完全背包)

题目描述：

大家都知道在dota游戏中，装备是对于英雄来说十分重要的要素。
英雄们不仅可以购买单个的装备，甚至某些特定的装备组合能够合成更强的装备。
为了简化问题，我们将每个装备对于英雄的功能抽象为一个整数：价值。同时，如上所说，一些特定的装备可以用来合成更强的装备，玩家会因此获得除原装备价值外额外的价值。
给定玩家现有的金钱数，每个装备的价格和其对应的价值，以及装备合成的信息。输出，其能获得的最大价值数。
注意：每件装备只能参与合成一件合成装备（即原装备参与合成后得到合成后的新装备，原装备消失），除非一次购买多个该种装备。

思路

1. 刚开始没看懂题目, 还以为是有依赖的背包问题, 后来看了解题报告才明白过来: 装备是没有购买上限的, 这就简单多了

2. 假如给定的装备只能取一件, 装备之间又能合成新装备, 那么这道题就难了

代码

#include <iostream>

#include <stdio.h>

#include <memory.h>

using namespace std;

int weight[];

int value[];

int dp[];

int n, m, g;

int main() {

    while(scanf("%d%d%d", &n, &m, &g) != EOF) {

        memset(weight, , sizeof(weight));

        memset(value, , sizeof(value));

        memset(dp, , sizeof(dp));

        for(int i = ; i < n; i ++) {

            scanf("%d%d", weight+i, value+i);

        }

        for(int i = ; i < m; i ++) {

            int q;

            scanf("%d", &q);

            for(int k = ; k < q; k ++) {

                int party;

                scanf("%d", &party);

                weight[n] += weight[party-];

                value[n] += value[party-];

            }

            int extraValue;

            scanf("%d", &extraValue);

            value[n] += extraValue;

            n++;

        }

        for(int i = ; i < n; i ++) {

            for(int v = weight[i]; v <= g; v ++) {

                dp[v] = max(dp[v], dp[v-weight[i]]+value[i]);

            }

        }

        printf("%d\n", dp[g]);

    }

    return ;

}

巴特西

九度 1494：Dota(完全背包)

最新文章

热门文章