首页 > 代码库 > hdu magic balls
hdu magic balls
magic balls
Time Limit: 6000/3000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 74 Accepted Submission(s): 10
Problem Description
The town of W has N people. Each person takes two magic balls A and B every day. Each ball has the volume ai and bi. People often stand together. The wizard will find the longest increasing subsequence in the ball A. The wizard has M energy. Each point of energy can change the two balls’ volume.(swap(ai,bi)).The wizard wants to know how to make the longest increasing subsequence and the energy is not negative in last. In order to simplify the problem, you only need to output how long the longest increasing subsequence is.
Input
The first line contains a single integer T(1≤T≤20)(the data for N>100 less than 6 cases), indicating the number of test cases.
Each test case begins with two integer N(1≤N≤1000) and M(0≤M≤1000),indicating the number of people and the number of the wizard’s energy. Next N lines contains two integer ai and bi(1≤ai,bi≤109),indicating the balls’ volume.
Each test case begins with two integer N(1≤N≤1000) and M(0≤M≤1000),indicating the number of people and the number of the wizard’s energy. Next N lines contains two integer ai and bi(1≤ai,bi≤109),indicating the balls’ volume.
Output
For each case, output an integer means how long the longest increasing subsequence is.
Sample Input
25 35 14 23 12 43 15 45 14 23 12 43 1
Sample Output
44
Source
BestCoder Round #20
思路: 建 m 棵线段树,里面维护的是权值,
PS :BC的pst好像都好水,写的时候那么大错误还过了。。
==
#include <stdio.h>#include <math.h>#include <string.h>#include <iostream>#include <vector>#include <map>#include <queue>#include <algorithm>#define LL long long#define maxn 2010#define INF 0x3f3f3f3f#define mod 1000000007using namespace std;int a[maxn],b[maxn],id[maxn] ;int ql,qr;short v ;struct node{ int n,mid,hehe[maxn]; short Max[maxn*4]; void init(int n ) { for(int i=1;i<=n*4;i++) Max[i]=0; for(int i=1;i<=n;i++) hehe[i]=0; } void insert(int L,int R,int o ) { if(L==R) { Max[o]=v; hehe[L]=v; return ; } mid=(L+R)>>1 ; if(ql<=mid) insert(L,mid,o<<1) ; else insert(mid+1,R,o<<1|1) ; Max[o]=max(Max[o<<1],Max[o<<1|1]); } void find(int L,int R,int o) { if(ql<=L&&qr>=R) { v=max(Max[o],v) ; return ; } mid=(L+R)>>1 ; if(ql<=mid) find(L,mid,o<<1) ; if(qr>mid) find(mid+1,R,o<<1|1) ; }}qe[1010] ;int main(){ int i,xx,yy,ans ; int j,n,m,pre,sz; int T,tmp,val; //freopen("in.txt","r",stdin); cin >> T ; while(T--) { scanf("%d%d",&n,&m) ; sz=0; for( i = 1 ; i <= n ;i++){ scanf("%d%d",&a[i],&b[i]) ; id[sz++]=a[i]; id[sz++]=b[i]; } sort(id,id+sz) ; sz=unique(id,id+sz)-id; ans=0; for( i = 0; i <= m;i++) { qe[i].init(sz); } for( i = 1 ; i <= n ;i++) { a[i]=lower_bound(id,id+sz,a[i])-id; b[i]=lower_bound(id,id+sz,b[i])-id; a[i]++;b[i]++; for( j = min(i,m); j >= 0 ;j--) { ql=1; qr=a[i]-1; v=0; if(ql<=qr) qe[j].find(1,sz,1) ; ql=a[i] ; v=v+1; tmp=v; if(qe[j].hehe[ql]<v)qe[j].insert(1,sz,1); if(j>0){ ql=1; qr=b[i]-1; v=0; if(ql<=qr) qe[j-1].find(1,sz,1) ; ql=b[i] ; v=v+1; tmp=max(tmp,(int)v); if(qe[j].hehe[ql]<v)qe[j].insert(1,sz,1); } ans=max(ans,tmp); } } cout<<ans<<endl; } return 0 ;}
hdu magic balls
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。