3804. [JZOI 2022 day2]鲍勃打比赛

【题目描述】

终于，鲍勃的算法和编程水平都有了不小的进步，他决定参加 $noip$ 来测试自己的水平。为了练习，爱丽丝老师为他准备了 $n$ 场训练赛，第 $i$ 场的难度是 $a_i$, 鲍勃可以从第 $1$ 场开始，依次考虑参加不参加。

他参加比赛的规则如下：

如果鲍勃同时参加了比赛 $i,j (i < j)$ 则应该有 $a_i <= a_j$；

如果鲍勃没有参加比赛 $i$, 并且这是连续第 $k$ 场没有参加的比赛，他将丢失 $k$ 点能力值。

鲍勃最终获得的能力值是所有参加的比赛的难度和减去丢失的能力值的和。

爱丽丝老师想让你帮忙计算一下，鲍勃能获得的最大的能力值是多少？

【输入格式】

输入第一行一个 $T(1 ≤ T ≤ 5)$ 代表数据组数。

对于每组数据：

第一行一个整数 $n(1 ≤ n ≤ 10^5)$，代表比赛的个数

其后一行 $n$ 个整数 $a_i,(−10^9 ≤ ai ≤ 10^9)$，代表第 $i$ 个比赛的困难程度。

【输出格式】

对于每组数据，输出一行一个整数，代表鲍勃能获得的最大的能力值。

【样例输入】

2
7
1 3 2 7 3 2 4
7
-3 -4 -2 -2 -6 -8 -1

【样例1输出】

7
-11

【样例2输入输出】

点击下载样例2 

【数据规模与约定】

测试点 $1 ∼ 2$： $n ≤ 1000，|a_i| ≤ 10^9$；

测试点 $3 ∼ 5$： $n ≤ 10^5 ，|a_i| ≤ 10^3$；

测试点 $6 ∼ 7$： $n ≤ 10^5，ai 不为负$；

测试点 $8 ∼ 10$： $n ≤ 10^5，|a_i| ≤ 10^9$；

【来源】

焦作一中 NOIP 2022 模拟赛2022.11.23 pro4