HDU1087(树状数组求LIS)

时间:2021-05-13 19:27:34

题是水题,学习一下用树状数组求LIS。

先离散化一下,注意去重;然后就把a[i]作为下标,dp[i]作为值,max作为维护的运算插进树状数组即可。

如果是上升子序列,询问(a[i] - 1);如果是不下降子序列,询问(a[i])。

 

 1 const int maxn = 1e3 + 5;
 2 int n, m, a[maxn], b[maxn], dp[maxn], f[maxn];
 3 
 4 void Modify(int x, int val) {
 5     for (; x <= m; x += x&-x)
 6         f[x] = max(f[x], val);
 7 }
 8 
 9 int Query(int x) {
10     int ret = 0;
11     for (; x; x -= x&-x)
12         ret = max(f[x], ret);
13     return ret;
14 }
15 
16 int main() {
17     while (~scanf("%d", &n) && n) {
18         init(f, 0);
19         rep(i, 1, n)    read(a[i]), b[i] = a[i];
20         //离散化
21         sort(b + 1, b + 1 + n);
22         m = unique(b + 1, b + 1 + n) - b - 1;
23         rep(i, 1, n)    a[i] = lower_bound(b + 1, b + 1 + m, a[i]) - b;
24 
25         int ans = 0;
26         rep(i, 1, n) {
27             dp[i] = Query(a[i] - 1) + b[a[i]];
28             ans = max(ans, dp[i]);
29             Modify(a[i], dp[i]);
30         }
31 
32         writeln(ans);
33     }
34     return 0;
35 }