A7009. 最佳球队组建
编程题
普及/提高-
知识点
题目描述
现有 $n$ 名球员，第 $i$ 名球员（$1 \le i \le n$）具有两个属性：分数 $s_i$ 和年龄 $a_i$。
教练希望从这 $n$ 名球员中选出一个子集组成一支球队，使得球队中所有球员的分数之和最大。但是，球队的选拔必须遵循**无矛盾原则**：
对于球队中的任意两名球员 $i$ 和 $j$，若他们的年龄不同，则**年龄较小**的球员的分数**不得严格大于**年龄较大的球员。即：
若 $a_i < a_j$，则必须满足 $s_i \le s_j$。
如果两名球员年龄相同（$a_i = a_j$），则他们之间不会产生矛盾。
请计算出在满足无矛盾原则的前提下，球队所能达到的**最大分数之和**。
教练希望从这 $n$ 名球员中选出一个子集组成一支球队，使得球队中所有球员的分数之和最大。但是，球队的选拔必须遵循**无矛盾原则**：
对于球队中的任意两名球员 $i$ 和 $j$，若他们的年龄不同，则**年龄较小**的球员的分数**不得严格大于**年龄较大的球员。即：
若 $a_i < a_j$，则必须满足 $s_i \le s_j$。
如果两名球员年龄相同（$a_i = a_j$），则他们之间不会产生矛盾。
请计算出在满足无矛盾原则的前提下，球队所能达到的**最大分数之和**。
输入格式
输入共三行。
第一行包含一个正整数 $n$，表示球员的数量。
第二行包含 $n$ 个正整数 $s_1, s_2, \dots, s_n$，表示每位球员的分数。
第三行包含 $n$ 个正整数 $a_1, a_2, \dots, a_n$，表示每位球员的年龄。
第一行包含一个正整数 $n$，表示球员的数量。
第二行包含 $n$ 个正整数 $s_1, s_2, \dots, s_n$，表示每位球员的分数。
第三行包含 $n$ 个正整数 $a_1, a_2, \dots, a_n$，表示每位球员的年龄。
输出格式
输出一个整数，表示无矛盾球队的最大总得分。
输入输出样例
输入 #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 \le n \le 1000$
- $1 \le s_i \le 10^6$
- $1 \le a_i \le 1000$
最优方案是选择第 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 \le n \le 1000$
- $1 \le s_i \le 10^6$
- $1 \le a_i \le 1000$