A94870.最佳球队组建
普及/提高-
通过率:0%
时间限制:1.00s
内存限制:128MB
题目描述
现有 n 名球员,第 i 名球员(1≤i≤n)具有两个属性:分数 si 和年龄 ai。
教练希望从这 n 名球员中选出一个子集组成一支球队,使得球队中所有球员的分数之和最大。但是,球队的选拔必须遵循无矛盾原则:
对于球队中的任意两名球员 i 和 j,若他们的年龄不同,则年龄较小的球员的分数不得严格大于年龄较大的球员。即:
若 ai<aj,则必须满足 si≤sj。
如果两名球员年龄相同(ai=aj),则他们之间不会产生矛盾。
请计算出在满足无矛盾原则的前提下,球队所能达到的最大分数之和。
输入格式
输入共三行。
第一行包含一个正整数 n,表示球员的数量。
第二行包含 n 个正整数 s1,s2,…,sn,表示每位球员的分数。
第三行包含 n 个正整数 a1,a2,…,an,表示每位球员的年龄。
输出格式
输出一个整数,表示无矛盾球队的最大总得分。
输入输出样例
输入#1
5 1 3 5 10 15 1 2 3 4 5
输出#1
34
输入#2
4 4 5 6 5 2 1 2 1
输出#2
16
输入#3
4 1 2 3 5 8 9 10 1
输出#3
6
说明/提示
【样例解释 2】
最优方案是选择第 2、3、4 名球员(下标从 1 开始):
- 球员 2:分数 5,年龄 1
- 球员 3:分数 6,年龄 2
- 球员 4:分数 5,年龄 1
总分:5+6+5=16。
其中球员 2 和 4 年龄相同(均为 1),无冲突;球员 3 年龄为 2,且分数 6 大于年龄为 1 的球员分数,符合规则。
【数据范围】
对于 100% 的数据,满足:
- 1≤n≤1000
- 1≤si≤106
- 1≤ai≤1000