A14149. Skyline Photo
编程题
普及/提高-
知识点
题目描述
Alice is visiting New York City. To make the trip fun, Alice will take photos of the city skyline and give the set of photos as a present to Bob. However, she wants to find the set of photos with maximum beauty and she needs your help.
There are $n$ buildings in the city, the $i$ -th of them has positive height $h_i$ . All $n$ building heights in the city are different. In addition, each building has a beauty value $b_i$ . Note that beauty can be positive or negative, as there are ugly buildings in the city too.
A set of photos consists of one or more photos of the buildings in the skyline. Each photo includes one or more buildings in the skyline that form a contiguous segment of indices. Each building needs to be in exactly one photo. This means that if a building does not appear in any photo, or if a building appears in more than one photo, the set of pictures is not valid.
The beauty of a photo is equivalent to the beauty $b_i$ of the shortest building in it. The total beauty of a set of photos is the sum of the beauty of all photos in it. Help Alice to find the maximum beauty a valid set of photos can have.
There are $n$ buildings in the city, the $i$ -th of them has positive height $h_i$ . All $n$ building heights in the city are different. In addition, each building has a beauty value $b_i$ . Note that beauty can be positive or negative, as there are ugly buildings in the city too.
A set of photos consists of one or more photos of the buildings in the skyline. Each photo includes one or more buildings in the skyline that form a contiguous segment of indices. Each building needs to be in exactly one photo. This means that if a building does not appear in any photo, or if a building appears in more than one photo, the set of pictures is not valid.
The beauty of a photo is equivalent to the beauty $b_i$ of the shortest building in it. The total beauty of a set of photos is the sum of the beauty of all photos in it. Help Alice to find the maximum beauty a valid set of photos can have.
输入格式
The first line contains an integer $n$ ( $1 \le n \le 3 \cdot 10^5$ ), the number of buildings on the skyline.
The second line contains $n$ distinct integers $h_1, h_2, \ldots, h_n$ ( $1 \le h_i \le n$ ). The $i$ -th number represents the height of building $i$ .
The third line contains $n$ integers $b_1, b_2, \ldots, b_n$ ( $-10^9 \le b_i \le 10^9$ ). The $i$ -th number represents the beauty of building $i$ .
The second line contains $n$ distinct integers $h_1, h_2, \ldots, h_n$ ( $1 \le h_i \le n$ ). The $i$ -th number represents the height of building $i$ .
The third line contains $n$ integers $b_1, b_2, \ldots, b_n$ ( $-10^9 \le b_i \le 10^9$ ). The $i$ -th number represents the beauty of building $i$ .
输出格式
Print one number representing the maximum beauty Alice can achieve for a valid set of photos of the skyline.
输入输出样例
输入 #1
5 1 2 3 5 4 1 5 3 2 4
输出 #1
15
输入 #2
5 1 4 3 2 5 -3 4 -10 2 7
输出 #2
10
输入 #3
2 2 1 -2 -3
输出 #3
-3
输入 #4
10 4 7 3 2 5 1 9 10 6 8 -4 40 -46 -8 -16 4 -10 41 12 3
输出 #4
96
说明/提示
In the first example, Alice can achieve maximum beauty by taking five photos, each one containing one building.
In the second example, Alice can achieve a maximum beauty of $10$ by taking four pictures: three just containing one building, on buildings $1$ , $2$ and $5$ , each photo with beauty $-3$ , $4$ and $7$ respectively, and another photo containing building $3$ and $4$ , with beauty $2$ .
In the third example, Alice will just take one picture of the whole city.
In the fourth example, Alice can take the following pictures to achieve maximum beauty: photos with just one building on buildings $1$ , $2$ , $8$ , $9$ , and $10$ , and a single photo of buildings $3$ , $4$ , $5$ , $6$ , and $7$ .
In the second example, Alice can achieve a maximum beauty of $10$ by taking four pictures: three just containing one building, on buildings $1$ , $2$ and $5$ , each photo with beauty $-3$ , $4$ and $7$ respectively, and another photo containing building $3$ and $4$ , with beauty $2$ .
In the third example, Alice will just take one picture of the whole city.
In the fourth example, Alice can take the following pictures to achieve maximum beauty: photos with just one building on buildings $1$ , $2$ , $8$ , $9$ , and $10$ , and a single photo of buildings $3$ , $4$ , $5$ , $6$ , and $7$ .