题目描述：
给定一个长度为 $ n $ 的整数序列 $ a_1, a_2,\cdots,a_n $ 。选出一个该序列的严格上升子序列，并且子序列各元素的和尽可能大。请问最大值是多少？
数据范围：
$ 1\le n \le 10^5,1\le a_i\le 10^9 $
题解：
很容易想到使用动态规划，容易想到线性dp方程
但是需要双层循环，而 $ n $ 比较大，时间爆炸。因此需要优化，容易想到使用树状数组或线段树。这里使用树状数组。使用树状数组需要维护 $ [1, a[i] - 1] $ 的最大值。但是 $ a[i] $ 太大了，需要离散化。
离散化
离散化将原数组映射到一个数值比较小的连续的新数组。一般有两种方式。
第一种方法，使用 $ unordered\_map $ ：
1
2
3
4
5
| int size = 0;
for(int i = 0; i < n; ++i)
{
if(!mp.count(a[i])) mp[a[i]] = size++;
}
|
可以 $ size++ $ 得到 $ [0,size-1] $ 的新数组，也可以 $ ++size $ ，得到 $ [1,size] $ 的新数组。注意如果要保持大小关系，可以提前排序。
对于下标 $ i $ ，原数组值 $ a[i] $ ，新数组值 $ mp[a[i]] $ 。
第二种方法，使用 $ sort,unique,lower\_bound $ ：
1
2
3
4
5
6
7
| b = a;
sort(b, b+n);
int size = unique(b, b + n) - b;
for(int i = 0; i < n; ++i)
{
a[i] = lower_bound(b, b + size, a[i]) - b;
}
|
这样得到的新数组的值是 $ [0,size - 1] $ ，也可以先在 $ b[n] $ 存入一个非常小的值，然后排序。得到 $ [1,size] $
通过二分查找得到了新的数组，对于下标 $ i $ ，原数组值 $ b[a[i]] $ ，新数组值 $ a[i] $
总的来说，还是 $ map $ 比较简单，但是速度会慢一点。
代码：
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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
| using namespace std;
using namespace FAST_IO;
const ll mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const ll INF_LL = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-5;
const int maxn = 1e5 + 10;
const int maxm = 1e5 + 10;
int t, n, m, k;
int a[maxn];
ll dp[maxn];
ll max_size, c[maxn];
int lowbit(int x)
{
return x & -x;
}
void insert(int index, ll val)
{
while (index <= max_size)
{
c[index] = max(c[index], val);
index += lowbit(index);
}
}
ll query(int index)
{
ll ans = 0;
while (index >= 1)
{
ans = max(ans, c[index]);
index -= lowbit(index);
}
return ans;
}
int b[maxn];
int main()
{
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
#endif
ios::sync_with_stdio(false);
cin.tie(0);
read(n);
for (int i = 0; i < n; ++i)
{
read(a[i]);
b[i] = a[i];
}
b[n] = -1e9 - 1;
sort(b, b + n + 1);
int size = unique(b, b + n + 1) - b;
for (int i = 0; i < n; ++i)
{
a[i] = lower_bound(b, b + size, a[i]) - b;
}
max_size = size;
ll ans = 0;
for (int i = 0; i < n; ++i)
{
dp[i] = query(a[i] - 1) + b[a[i]];
insert(a[i], dp[i]);
ans = max(ans, dp[i]);
}
cout << ans << endl;
return 0;
}
|