题目大意：给你n只老鼠的体重w和速度s，让你找出最长的子序列使得w[i] < w[j] 且 s[i] > s[j] (i < j)。求最长序列的长度并输出该序列。
LIS(Longest Increasing Subsequence)问题，先对老鼠进行排序，以w为第一关键字从小到大排序，再以s为第二关键字从大到小排序，然后就是LIS问题的处理了。LIS(i)表示以a[i]结尾的最长增长序列的长度。
#include <cstdio>
#include <algorithm>
using namespace std; struct Mouse
{
int id, w, s;
bool operator < (const Mouse &m) const
{
if (w != m.w) return w < m.w;
return s > m.s;
}
} mouse[];
int lis[], pre[]; void print_lis(int p)
{
if (pre[p] != -) print_lis(pre[p]);
printf("%d\n", mouse[p].id);
} int main()
{
#ifdef LOCAL
freopen("in", "r", stdin);
#endif
int n = , a, b;
while (scanf("%d%d", &a, &b) != EOF)
{
mouse[n].w = a;
mouse[n].s = b;
mouse[n].id = n + ;
n++;
}
sort(mouse, mouse+n);
lis[] = ;
int p = ;
for (int i = ; i < n; i++)
pre[i] = -;
for (int i = ; i < n; i++)
{
lis[i] = ;
for (int j = ; j < i; j++)
if (mouse[i].w > mouse[j].w && mouse[i].s < mouse[j].s)
{
if (lis[j]+ > lis[i])
{
lis[i] = lis[j] + ;
pre[i] = j;
}
}
if (lis[i] > lis[p]) p = i;
}
printf("%d\n", lis[p]);
print_lis(p);
return ;
}