POJ 1065 Wooden Sticks

题目传送门

解题思路:

将w从小到大排序,当w相等时,l较小的在前面,以l为基准求LIS.

AC代码:

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<algorithm>
 4 #include<cstring>
 5 
 6 using namespace std;
 7 
 8 const int INF = 1e9;
 9 
10 int t,n,f[5001],len,ans[5001],a[5001]; 
11 struct kkk {
12     int w,l;
13 }e[5001];
14 
15 bool cmp(kkk a,kkk b) {
16     if(a.w == b.w) return a.l < b.l;
17     return a.w < b.w;
18 }
19 
20 bool cmp1(int a,int b) {
21     return a > b;
22 }
23 
24 inline void solve() {
25     len = 1;
26     sort(e+1,e+n+1,cmp);
27     for(int i = 1;i <= n; i++) a[i] = e[i].l,ans[i] = -INF;
28     for (int i = 1; i <= n; ++i) {
29            if (a[i] < ans[len]) 
30             ans[++len] = a[i];
31         else {
32                 int pos = lower_bound(ans + 1, ans + len + 1, a[i],cmp1) - ans;
33             ans[pos] = a[i];
34         }
35     }
36 }
37 
38 int main()
39 {
40     scanf("%d",&t);
41     while(t--) {
42         scanf("%d",&n);
43         for(int i = 1;i <= n; i++) 
44             scanf("%d%d",&e[i].l,&e[i].w);
45         solve();
46         printf("%d
",len);    
47     }
48     return 0;
49 }