#P1791. [国家集训队] 人员雇佣
[国家集训队] 人员雇佣
题目背景
原《线段覆盖》请做P1803
题目描述
作为一个富有经营头脑的富翁,小 决定从本国最优秀的经理中雇佣一些来经营自己的公司。这些经理相互之间合作有一个贡献指数,(我们用 表示 经理对 经理的了解程度),即当经理 和经理 同时被雇佣时,经理 会对经理 做出贡献,使得所赚得的利润增加 。
当然,雇佣每一个经理都需要花费一定的金钱 ,对于一些经理可能他做出的贡献不值得他的花费,那么作为一个聪明的人,小 当然不会雇佣他。然而,那些没有被雇佣的人会被竞争对手所雇佣,这个时候那些人会对你雇佣的经理的工作造成影响,使得所赚得的利润减少 (注意:这里的 与上面的 是同一个)。
作为一个效率优先的人,小 想雇佣一些人使得净利润最大。你可以帮助小 解决这个问题吗?
输入格式
第一行有一个整数,表示经理的个数。
第二行有 个整数 表示雇佣每个经理需要花费的金钱。
接下来的 行中一行包含 个数,表示 ,即经理 对经理 的了解程度。满足 。
输出格式
第一行包含一个整数,即所求出的最大值。
3
3 5 100
0 6 1
6 0 2
1 2 0
1
提示
- 的数据中 ;
- 的数据中 ;
- 的数据中 ,,。
From 林衍凯。