CF1482E Skyline Photo

Alice 正在游览纽约市。为了让这次旅行更有趣，Alice 决定拍摄城市天际线的照片，并将这组照片作为礼物送给 Bob。然而，她希望找到一组美丽值最大的照片集，因此需要你的帮助。 城市中有 $n$ 栋建筑，第 $i$ 栋的高度为正整数 $h_i$。城市中所有 $n$ 栋建筑的高度各不相同。此外，每栋建筑还有一个美丽值 $b_i$。注意，美丽值可以为正也可以为负，因为城市中也有丑陋的建筑。 一组照片由一张或多张天际线建筑的照片组成。每张照片包含天际线上一段连续编号的建筑。每栋建筑必须且只能出现在一张照片中。这意味着如果某栋建筑没有出现在任何照片中，或者出现在多张照片中，则这组照片是无效的。 一张照片的美丽值等于其中最矮建筑的美丽值 $b_i$。一组照片的总美丽值是所有照片美丽值的和。请帮助 Alice 找到一组有效照片集，使其总美丽值最大。

第一行包含一个整数 $n$（$1 \le n \le 3 \times 10^5$），表示天际线上建筑的数量。 第二行包含 $n$ 个互不相同的整数 $h_1, h_2, \ldots, h_n$（$1 \le h_i \le n$），第 $i$ 个数表示第 $i$ 栋建筑的高度。 第三行包含 $n$ 个整数 $b_1, b_2, \ldots, b_n$（$-10^9 \le b_i \le 10^9$），第 $i$ 个数表示第 $i$ 栋建筑的美丽值。

输出一个整数，表示 Alice 能获得的有效照片集的最大总美丽值。

在第一个样例中，Alice 可以通过拍摄五张照片，每张照片只包含一栋建筑，从而获得最大美丽值。 在第二个样例中，Alice 可以通过拍摄四张照片获得最大美丽值 $10$：其中三张照片分别只包含第 $1$、$2$、$5$ 栋建筑，每张照片的美丽值分别为 $-3$、$4$、$7$，另一张照片包含第 $3$ 和第 $4$ 栋建筑，这张照片的美丽值为 $2$。 在第三个样例中，Alice 只需拍摄一张包含全部建筑的照片。 在第四个样例中，Alice 可以通过如下方式获得最大美丽值：分别拍摄只包含第 $1$、$2$、$8$、$9$、$10$ 栋建筑的照片，以及一张包含第 $3$ 到第 $7$ 栋建筑的照片。 由 ChatGPT 4.1 翻译