题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1051
贪心策略，按照l为第一关键字，w为第二关键字排序，在排序后的w数组中寻找不下降子序列的个数即可（因为此时l数组单调不下降一定满足题目条件）。
有一个结论：单调不下降（不上升）子序列的数目等于最长单调下降（上升）子序列的长度，用树状数组求解LIS即可。
LIS问题用树状数组求解，树状数组直接维护前i-1个序列元素的LIS的最大值，树状数组的下标对应序列元素的高度（这样可以直接查询高度大于(等于)或小于(等于)个高度的LIS的最大值），序列下标较小的元素先进树状数组，保证了树状数组里查询到的结果一定是前i-1个元素而非之后的元素的。
看到这题的n为5000，感觉n^2肯定会炸，就写了一个LIS，结果发现其实交一个暴力的话只需要15ms，心情复杂.jpg
LIS树状数组做法1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
using namespace std;
const int maxn=5009;
const int maxl=10009;
const int mw=10001;
struct W {
int a,b;
bool operator <(const W& y) const {
if(a!=y.a) return a<y.a;
else return b<y.b;
}
}w[maxn];
int n;
int f[maxn];
int t[maxl];
int lowbit(int x) {
return x&-x;
}
void add(int x,int val) {
while(x<maxl) {
t[x]=max(t[x],val);
x+=lowbit(x);
}
}
int query(int x) {
int ans=-2147483648;
while(x) {
ans=max(ans,t[x]);
x-=lowbit(x);
}
return ans;
}
int main() {
int T;
scanf("%d",&T);
while(T--) {
memset(f,0,sizeof(f));
memset(t,0,sizeof(t));
scanf("%d",&n);
for(int i=1;i<=n;i++) {
scanf("%d%d",&w[i].a,&w[i].b);
}
int mx=0;
sort(w+1,w+n+1);
for(int i=1;i<=n;i++) {
f[i]=query(mw-(w[i].b+1))+1;
mx=max(mx,f[i]);
add(mw-(w[i].b),f[i]);
}
printf("%d\n",mx);
}
}
暴力做法1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
using namespace std;
const int maxn=5009;
struct W {
int a,b;
bool operator <(const W& y) const {
if(a!=y.a) return a<y.a;
else return b<y.b;
}
}w[maxn];
int n;
bool vis[maxn];
int main() {
int T;
scanf("%d",&T);
while(T--) {
scanf("%d",&n);
memset(vis,0,sizeof(vis));
for(int i=1;i<=n;i++) {
scanf("%d%d",&w[i].a,&w[i].b);
}
sort(w+1,w+n+1);
int cnt=0,x;
for(int i=1;i<=n;i++)
if(!vis[i]) {
vis[i]=1;
cnt++;
x=w[i].b;
for(int j=i+1;j<=n;j++)
if(w[j].b>=x && !vis[j]) x=w[j].b,vis[j]=1;
}
printf("%d\n",cnt);
}
}