HDU5125--magic balls（LIS）

题意：求a数组的LIS，但是加了一个条件，为了LIS最大 b[i] a[i]可以交换。最多交换mci；

赤果果的dp啊，可是这个题用线段树的话却会TLE，，由于查询的只是1-x的最大值因此我们可以用树状数组来查询最值，话说树状数组真的比线段树快乐好多啊。

本地随机数据，线段树2.7s左右，，树状数组不到1s。。。

大致思路：建m个树状数组，对于位置i的数字有两种状态①交换a b②不交换。两种情况分开，

Code：

 1 #include <cstdio>
 2 #include <string>
 3 #include <vector>
 4 #include <cstdlib>
 5 #include <cstring>
 6 #include <iostream>
 7 #include <algorithm>
 8 using namespace std;
 9 const int maxn = 1005;
10 int a[maxn],b[maxn];
11 int c[maxn][maxn<<1];
12 int vec[maxn<<1],idx;
13 inline int lowbit (int x)
14 {
15     return x & -x;
16 }
17 void add(int x,int d,int k)
18 {
19     while (x < 2*maxn)
20     {
21         c[k][x] = max(d,c[k][x]);
22         x += lowbit(x);
23     }
24 }
25 int get_max(int x,int k)
26 {
27     int res = 0;
28     while (x)
29     {
30         res = max(res,c[k][x]);
31         x -= lowbit(x);
32     }
33     return res;
34 }
35 int hash_(int x)
36 {
37     return lower_bound(vec,vec+idx,x) - vec + 2;
38 }
39 
40 int main(void)
41 {
42 #ifndef ONLINE_JUDGE
43     freopen("in.txt","r",stdin);
44 #endif
45     int t;
46     scanf ("%d",&t);
47     while (t--)
48     {
49         int n,m;
50         scanf ("%d%d",&n,&m);
51         m = min(n,m);
52         idx = 0;
53         memset(c,0,sizeof(c));
54         for (int i = 0; i < n; i++)
55         {
56             scanf ("%d%d",a+i,b+i);
57             vec[idx++] = a[i];
58             vec[idx++] = b[i];
59         }
60         sort(vec,vec+idx);
61         idx = unique(vec,vec+idx) - vec;
62         for (int i = 0; i< n; i++)
63         {
64             a[i] = hash_(a[i]);
65             b[i] = hash_(b[i]);
66         }
67         int ans = 1;
68         for (int i = 0; i < n ; i++)
69         {
70             for (int j = 0; j <= m; j++)
71             {
72                 int tmp = 1;
73                 tmp += get_max(a[i]-1,j);
74                 add(a[i],tmp,j);
75                 ans = max(tmp,ans);
76                 if (j)
77                 {
78                     tmp = 1;
79                     tmp += get_max(b[i]-1,j+1);
80                     add(b[i],tmp,j);
81                     ans = max(tmp,ans);
82                 }
83             }
84         }
85         printf("%d
",ans);
86     }
87     return 0;
88 }

附树状数组求最值模板。！！此时求最大值时修改操作只能改大，不可以改小。求最小值时相反。

 1 int lowbit (int x)
 2 {
 3     return x & -x;
 4 }
 5 int c[N];
 6 void add(int x,int val)       //    位置i的数更新为val
 7 {
 8     while (x < N)
 9     {
10         c[x] = max(c[x],val);
11         x += lowbit(x);
12     }
13 }
14 int get_max(int x)
15 {
16     int res = 0;            //这个0 不是固定的，，取一个较小的数就可以了。
17     while (x) 
18     {
19         res = max(res,c[x]);
20         x -= lowbit(x);
21     }
22     return res;
23 }

代码如下