### 题目描述

Some people think that the bigger an elephant is, the smarter it is. To disprove this, you want to analyze a collection of elephants and place as large a subset of elephants as possible into a sequence whose weights are increasing but IQ’s are decreasing.

### 输入

The input will consist of data for a bunch of elephants, at one elephant per line terminated by the end-of-file. The data for each particular elephant will consist of a pair of integers: the first representing its size in kilograms and the second representing its IQ in hundredths of IQ points. Both integers are between 1 and 10,000. The data contains information on at most 1,000 elephants. Two elephants may have the same weight, the same IQ, or even the same weight and IQ.

### 输出

The first output line should contain an integer n, the length of elephant sequence found. The remaining n lines should each contain a single positive integer representing an elephant. Denote the numbers on the ith data line as W[i] and S[i]. If these sequence of n elephants are a[1], a[2],…, a[n] then it must be the case that W[a[1]] < W[a[2]] < … < W[a[n]] and S[a[1]] > S[a[2]] > … > S[a[n]] In order for the answer to be correct, n must be as large as possible. All inequalities are strict: weights must be strictly increasing, and IQs must be strictly decreasing. Your program can report any correct answer for a given input.

6008 1300
6000 2100
500 2000
1000 4000
1100 3000
6000 2000
8000 1400
6000 1200
2000 1900

4
4
5
9
7

### 代码如下

``````#include<stdio.h>
#define N 1005
FILE *f1,*f2;
typedef struct node
{
long w,s,num;
}node;
node a[N];
long f[N],b[N],q[N],n;

int bigger(node x,node y)
{
if (x.w!=y.w) return (x.w>y.w);
else return (x.s<y.s);
}

void sort(long left,long right)
{
long i,j;
node x,t;
i=left;j=right;
x=a[(i+j)/2];
while (i<=j)
{
while (bigger(x,a[i])) i++;
while (bigger(a[j],x)) j--;
if (i<=j)
{     t=a[i];a[i]=a[j];a[j]=t;
i++;j--;
}
}
if (left<j) sort(left,j);
if (i<right) sort(i,right);
}
int main()
{
long i,j,k,max;
i=1;
while (scanf("%ld%ld",&a[i].w,&a[i].s)==2)  a[i].num=i++;
n=i-1;
sort(1,n);
for (i=1;i<=n;i++) {f[i]=1;b[i]=i;}
for (i=1;i<=n;i++)
for (j=1;j<i;j++)
if (a[j].w<a[i].w&&a[j].s>a[i].s&&f[j]+1>f[i])
{  f[i]=f[j]+1; b[i]=j; }
max=0;
for (i=1;i<=n;i++)
if (f[i]>max) {max=f[i];k=i;}
printf("%ld\n",max);
q[1]=a[k].num; i=1;
while (b[k]!=k) {q[++i]=a[b[k]].num; k=b[k];}
for (i=max;i>=1;i--)
printf("%ld\n",q[i]);
return 0;
}
``````