#P13322. [2025年队测]孙子兵法
[2025年队测]孙子兵法
题目描述
wshcl 和 ET-G 分别带领一支队伍。 个人依次上场,他们的战力值 构成 的一个排列。每个人必须分配到其中一支队伍。
- 分配到 wshcl 队伍的人,若其战力值大于该队此前所有上场者的战力值,就对敌方造成一点伤害。
- 分配到 ET-G 队伍的人,若其战力值小于该队此前所有上场者的战力值,就对敌方造成一点伤害。
每支队伍的首位上场者满足该队的条件。求在所有分配方案中,两支队伍合计能造成的最大伤害。
输入格式
第一行一个正整数 。
第二行 个正整数 ,依次表示各人的战力值。
输出格式
输出一行一个整数,表示最大总伤害。
样例
3
1 2 3
3
5
4 1 2 3 5
5
战力值为 的人分配给 wshcl,战力值为 的人分配给 ET-G,两队分别造成 和 点伤害。
6
4 2 5 1 6 3
5
战力值为 的人分配给 wshcl,战力值为 的人分配给 ET-G,两队分别造成 和 点伤害。
10
3 8 10 4 1 2 7 9 5 6
6
战力值为 的人分配给 wshcl,战力值为 的人分配给 ET-G,两队各造成 点伤害。
原题的样例 5 另见赛时选手目录 shung/shung5.in 与 shung/shung5.ans。
数据范围
对于全部数据,, 是 的一个排列。
| 测试点 | 的上限 | 特殊性质 |
|---|---|---|
| 1~2 | 无 | |
| 3~6 | ||
| 7~13 | ||
| 14~16 | ||
| 17~18 | 排列随机 | |
| 19~20 | 最长下降子序列长度不超过 | |
| 21~23 | 无 | |
| 24~25 |