首页 > 代码库 > HDU5125--magic balls（LIS）
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_JUDGE43 freopen("in.txt","r",stdin);44 #endif45 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\n",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 }
代码如下
HDU5125--magic balls（LIS）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。