2934. 最大高楼和
摘要
Title: 2934. 最大高楼和
Tag: dp、树状数组
Memory Limit: 64 MB
Time Limit: 1000 ms
Powered by:NEFU AB-IN
2934. 最大高楼和
-
题意
从这一堆高楼中，选出若干栋高楼，在保证高楼的高度是 严格递增 的情况下它们的 高度和最大 能是多少？
-
思路
最大上升子序列和问题，代码完全相同
https://hexo.ab-in.cn/2023/03/25/Acwing2023-3-25-1/ -
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55'''
Author: NEFU AB-IN
Date: 2023-03-26 10:14:42
FilePath: \Acwing\3662\3662.py
LastEditTime: 2023-03-26 10:37:30
'''
# import
import sys
from collections import Counter, deque
from heapq import heappop, heappush
from bisect import bisect_left, bisect_right
# Final
N = int(1e5 + 10)
INF = int(2e9)
# Define
sys.setrecursionlimit(INF)
read = lambda: map(int, input().split())
tr = [0] * N
def lowbit(x):
return x & -x
def add(x, v):
while x < N:
tr[x] = max(tr[x], v)
x += lowbit(x)
def query(x):
res = 0
while x:
res = max(res, tr[x])
x -= lowbit(x)
return res
n, = read()
a = list(read())
xs = a[:]
xs = sorted(list(set(xs)))
res = 0
for i in range(n):
k = bisect_left(xs, a[i]) + 1 # 保证下标大于0
s = query(k - 1) + a[i]
res = max(res, s)
add(k, s)
print(res)