A7009 | 最佳球队组建
时间限制1s
内存限制128MB
通过 / 提交0/0
题目描述
现有 $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$
C++ 编辑器
输入
输出
可保存默认模板；新题优先使用已保存模板。
当前快捷键仅展示，暂不支持修改。
- 撤销
Ctrl / ⌘ + Z - 重做
Ctrl / ⌘ + Y - 查找
Ctrl / ⌘ + F - 全选
Ctrl / ⌘ + A - 复制
Ctrl / ⌘ + C - 剪切
Ctrl / ⌘ + X - 粘贴
Ctrl / ⌘ + V - 自动排版
工具栏排版按钮 - 草稿保存
编辑时自动保存到本机
历史
提交记录
状态说明时间源码
AI
作答助手
你好，我是作答助手。可以问思路、复杂度、样例含义或代码报错原因；不会直接给出完整 AC 代码。
确定要清空代码吗？