AT_dp_q Flowers

题目描述

有 $N$ 朵花排成一排。对于每个 $i$（$1 \leq i \leq N$），从左往右第 $i$ 朵花的高度为 $h_i$，美丽值为 $a_i$。其中 $h_1, h_2, \ldots, h_N$ 互不相同。

太郎君想通过拔掉一些花，使得剩下的花满足以下条件：

• 从左到右看，剩下的花的高度严格递增。

请你求出剩下的花的美丽值总和的最大值。

输入格式

输入以如下格式从标准输入读入：

$N$
$h_1\ h_2\ \ldots\ h_N$
$a_1\ a_2\ \ldots\ a_N$

输出格式

请输出剩下的花的美丽值总和的最大值。

输入输出样例 #1

输入 #1

4
3 1 4 2
10 20 30 40

输出 #1

60

输入输出样例 #2

输入 #2

1
1
10

输出 #2

10

输入输出样例 #3

输入 #3

5
1 2 3 4 5
1000000000 1000000000 1000000000 1000000000 1000000000

输出 #3

5000000000

输入输出样例 #4

输入 #4

9
4 2 5 8 3 6 1 7 9
6 8 8 4 6 3 5 7 5

输出 #4

31

说明/提示

限制条件

• 所有输入均为整数。
• $1 \leq N \leq 2 \times 10^5$
• $1 \leq h_i \leq N$
• $h_1, h_2, \ldots, h_N$ 互不相同。
• $1 \leq a_i \leq 10^9$

样例解释 1

保留从左到右第 $2$、$4$ 朵花即可。此时高度依次为 $1, 2$，满足严格递增。美丽值总和为 $20 + 40 = 60$。

样例解释 2

一开始就已经满足条件。

样例解释 3

答案可能超出 32 位整数范围。

样例解释 4

保留从左到右第 $2$、$3$、$6$、$8$、$9$ 朵花即可。

由 ChatGPT 4.1 翻译