P4095 [HEOI2013]Eden 的新背包问题

    • 69通过
    • 126提交
  • 题目提供者 Drench 站长团
  • 评测方式 云端评测
  • 标签 背包 各省省选 2013 河北
  • 难度 提高+/省选-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目描述

    “ 寄 没 有 地 址 的 信 ,这 样 的 情 绪 有 种 距 离 ,你 放 着 谁 的 歌 曲 ,是 怎 样 的 心 情 。 能 不 能 说 给 我 听 。”

    失忆的 Eden 总想努力地回忆起过去,然而总是只能清晰地记得那种思念的 感觉,却不能回忆起她的音容笑貌。

    记忆中,她总是喜欢给 Eden 出谜题:在 valentine’s day 的夜晚,两人在闹市 中闲逛时,望着礼品店里精巧玲珑的各式玩偶,她突发奇想,问了 Eden 这样的 一个问题:有 n 个玩偶,每个玩偶有对应的价值、价钱,每个玩偶都可以被买有 限次,在携带的价钱 m 固定的情况下,如何选择买哪些玩偶以及每个玩偶买多 少个,才能使得选择的玩偶总价钱不超过 m,且价值和最大。

    众所周知的,这是一个很经典的多重背包问题,Eden 很快解决了,不过她似 乎因为自己的问题被飞快解决感到了一丝不高兴,于是她希望把问题加难:多次 询问,每次询问都将给出新的总价钱,并且会去掉某个玩偶(即这个玩偶不能被 选择),再问此时的多重背包的答案(即前一段所叙述的问题)。

    这下 Eden 犯难了,不过 Eden 不希望自己被难住,你能帮帮他么?

    输入输出格式

    输入格式:

    从文件 bag.in 看读入数据。 第一行一个数 n,表示有 n 个玩偶,玩偶从 0 开始编号

    第二行开始后面的 n 行,每行三个数 ai, bi, ci,分别表示买一个第 i 个玩偶需 要的价钱,获得的价值以及第 i 个玩偶的限购次数。

    接下来的一行为 q,表示询问次数。

    接下来 q 行,每行两个数 di, ei 表示每个询问去掉的是哪个玩偶(注意玩偶 从 0 开始编号)以及该询问对应的新的总价钱数。(去掉操作不保留,即不同询 问互相独立)

    输出格式:

    输出到文件 bag.out 中。 输出 q 行,第 i 行输出对于第 i 个询问的答案。

    输入输出样例

    输入样例#1: 复制
    5 
    2 3 4 
    1 2 1 
    4 1 2 
    2 1 1 
    3 2 3 
    5 
    1 10 
    2 7 
    3 4 
    4 8 
    0 5
    输出样例#1: 复制
    13 
    11 
    6 
    12 
    4 
    

    说明

    【样例说明】

    一共五种玩偶,分别的价钱价值和限购次数为(2,3,4), (1,2,1), (4,1,2), (2,1,1), (3,2,3)。

    五个询问,以第一个询问为例。

    第一个询问表示的是去掉编号为 1 的玩偶, 且拥有的钱数为 10 时可以获得的最大价值,则此时剩余玩偶为(2,3,4),(4,1,2), (2,1,1),(3,2,3),若把编号为 0 的玩偶买 4 个(即全买了),然后编号为 3 的玩偶 买一个,则刚好把 10 元全部花完,且总价值为 13。可以证明没有更优的方案了。

    注意买某种玩偶不一定要买光。

    【数据范围】

    10%数据满足 1 ≤ n ≤ 10;

    另 20%数据满足 1 ≤ n ≤ 100, ci = 1, 1 ≤ q ≤ 100;

    另 20%数据满足 1 ≤ n ≤ 100, 1 ≤ q ≤ 100;

    另 30%数据满足 ci = 1;

    100%数据满足 1 ≤ n ≤ 1000, 1 ≤ q ≤ 3*105, 1 ≤ ai、bi、ci ≤ 100, 0 ≤ di < n, 0 ≤ ei ≤ 1000。

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。