ZOJ 1025 Wooden Sticks

　　题目大意：有n个木棍，分别具有长度li和重量wi。对于木棍s1和s2，若l1<=l2且w1<=w2，则s1、s2可构成单调递增序列。求n个木棍中这样序列的个数。

　　最先的想法是，先排序，然后一遍一遍扫描，直到全部处理完。

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 using namespace std;
 5 #define MAXN 5000+10
 6 
 7 struct Wooden
 8 {
 9     int l, w;
10     bool operator < (const Wooden& x) const
11     {
12         if (l != x.l)   return l < x.l;
13         else return w < x.w;
14     }
15 };
16 Wooden wooden[MAXN];
17 bool processed[MAXN];
18 
19 int main()
20 {
21 #ifdef LOCAL
22     freopen("in", "r", stdin);
23 #endif
24     int T;
25     scanf("%d", &T);
26     while (T--)
27     {
28         int n;
29         scanf("%d", &n);
30         for (int i = 0; i < n; i++)
31             scanf("%d%d", &wooden[i].l, &wooden[i].w);
32         sort(wooden, wooden+n);
33         int time = 0;
34         memset(processed, 0, sizeof(processed));
35         int remain = n;
36         while (remain > 0)
37         {
38             time++;
39             int prel = -1, prew = -1;
40             for (int i = 0; i < n; i++)
41                 if (!processed[i] && wooden[i].l >= prel && wooden[i].w >= prew)
42                 {
43                     processed[i] = true;
44                     remain--;
45                     prel = wooden[i].l;
46                     prew = wooden[i].w;
47                 }
48         }
49         printf("%d
", time);
50     }
51     return 0;
52 }

View Code

　　看到网上说可以通过求解最长（严格）递减序列的答案，可是怎么都理解不了，留待以后吧...