2024湖北省赛VP
湖北省赛VP
https://codeforces.com/gym/105139/attachments/download/25287/Sol_ICPC_hubei_24.pdf
https://codeforces.com/gym/105139/attachments/download/25287/Sol_ICPC_hubei_24.pdf
高桥有 \[N\] 张纸牌,来自纸牌游戏 "AtCoder Magics"。其中的 \[i\] 张卡将被称为 \[i\] 张卡。每张卡都有两个参数:强度和成本。卡片 \[i\] 的强度为 \[A_i\] ,成本为 \[C_i\] 。
他不喜欢弱牌,所以他会弃掉它们。具体来说,他会重复下面的操作,直到无法再进行为止:
可以证明,当无法再进行操作时,剩下的牌的集合是唯一确定的。请找出这组牌。
爱丽丝和鲍勃正在商店里玩游戏。商店里有 \[n\] 件商品;每件商品有两个参数: \[a_i\] (爱丽丝的物品价格)和 \[b_i\] (鲍勃的物品价格)。
爱丽丝希望选择一个商品子集(可能是空)并购买它们。之后,Bob 会执行以下操作:
爱丽丝的利润等于 \[\sum\limits_{i \in S} b_i - \sum\limits_{j \in T} a_j\] ,其中\[S\] 是鲍勃从爱丽丝处购买的物品集, \[T\] 是爱丽丝从商店购买的物品集。换句话说,爱丽丝的利润就是鲍勃支付给她的金额和她购买商品所花费的金额之间的差额。
爱丽丝希望自己的利润最大化,而鲍勃希望爱丽丝的利润最小化。您的任务是计算在爱丽丝和鲍勃都采取最优行动的情况下爱丽丝的利润。
Problem - D - Codeforces