ZOJ 1108 & HDU 1160

　　题目大意：给你n只老鼠的体重w和速度s，让你找出最长的子序列使得w[i] < w[j] 且 s[i] > s[j] (i < j)。求最长序列的长度并输出该序列。

　　LIS(Longest Increasing Subsequence)问题，先对老鼠进行排序，以w为第一关键字从小到大排序，再以s为第二关键字从大到小排序，然后就是LIS问题的处理了。LIS(i)表示以a[i]结尾的最长增长序列的长度。

 1 #include <cstdio>
 2 #include <algorithm>
 3 using namespace std;
 4 
 5 struct Mouse
 6 {
 7     int id, w, s;
 8     bool operator < (const Mouse &m) const
 9     {
10         if (w != m.w)  return w < m.w;
11         return s > m.s;
12     }
13 } mouse[1100];
14 int lis[1100], pre[1100];
15 
16 void print_lis(int p)
17 {
18     if (pre[p] != -1)  print_lis(pre[p]);
19     printf("%d
", mouse[p].id);
20 }
21 
22 int main()
23 {
24 #ifdef LOCAL
25     freopen("in", "r", stdin);
26 #endif
27     int n = 0, a, b;
28     while (scanf("%d%d", &a, &b) != EOF)
29     {
30         mouse[n].w = a;
31         mouse[n].s = b;
32         mouse[n].id = n + 1;
33         n++;
34     }
35     sort(mouse, mouse+n);
36     lis[0] = 1;
37     int p = 0;
38     for (int i = 0; i < n; i++)
39         pre[i] = -1;
40     for (int i = 1; i < n; i++)
41     {
42         lis[i] = 1;
43         for (int j = 0; j < i; j++)
44             if (mouse[i].w > mouse[j].w && mouse[i].s < mouse[j].s)
45             {
46                 if (lis[j]+1 > lis[i])
47                 {
48                     lis[i] = lis[j] + 1;
49                     pre[i] = j;
50                 }
51             }
52         if (lis[i] > lis[p])  p = i;
53     }
54     printf("%d
", lis[p]);
55     print_lis(p);
56     return 0;
57 }
58

View Code