蛤蛤蛤（树状数组

蛤蛤蛤（树状数组 | 二分）

裸Lis

n²解法谁都会

下面是 nlogn 的解法

树状数组

 1 #include <cstdio>
 2 #include <algorithm>
 3 #include <iostream>
 4 #include <cstring>
 5 
 6 using namespace std;
 7 
 8 const int MAXN = 100001;
 9 int n, cnt, ans;
10 int a[MAXN], b[MAXN], c[MAXN];
11 
12 inline int query(int x)
13 {
14     int ans = 0;
15     for(; x; x -= x & -x) ans = max(ans, c[x]);
16     return ans;
17 }
18 
19 inline void update(int x, int d)
20 {
21     for(; x <= cnt; x += x & -x) c[x] = max(c[x], d);
22 }
23 
24 int main()
25 {
26     int i, j, x, y;
27     scanf("%d", &n);
28     for(i = 1; i <= n; i++) scanf("%d", &a[i]), b[i] = a[i];
29     sort(b + 1, b + n + 1);
30     cnt = unique(b + 1, b + n + 1) - (b + 1);
31     for(i = 1; i <= n; i++)
32     {
33         x = lower_bound(b + 1, b + cnt + 1, a[i]) - b;
34         y = query(x - 1) + 1;
35         update(x, y);
36         ans = max(ans, y);
37     }
38     printf("%d", n - ans);
39     return 0;
40 }

View Code

二分（原先的我真是naive）

 1 #include <cstdio>
 2 #include <iostream>
 3 
 4 using namespace std;
 5 
 6 int n, m, a[100011], b[100011], s, len, mid;
 7 
 8 int main()
 9 {
10     int i, j, k, x, y;
11     cin >> n;
12     for(i = 1; i <= n; i++)    cin >> a[i];
13     b[1] = a[1];
14     len = 1;
15     for(i = 2; i <= n; i++)
16     {
17         x = 1;
18         y = len;
19         while(x <= y)
20         {
21             mid = (x + y) / 2;
22             if(a[i] > b[mid]) x = mid + 1;
23             else y = mid - 1;
24         }
25         b[x] = a[i];
26         if(x > len) len = x;
27     }
28     cout << n - len;
29     return 0;
30 }

View Code