PersonalCorpus 版 (精华区)

40695 2002-10-11 13:43:55 Accepted
1108 C++ 00:00.01 424K Big Guava


int cmp(const void *a, const void *b)
{
    if (*(int *)a>*(int *)b) return 1;
    else if (*(int *)a==*(int *)b) return 0;
    else return -1;
}

int main()
{
#ifndef ONLINE_JUDGE
    freopen("c:\\0acm\\zju\\i1108","r",stdin);
    freopen("c:\\0acm\\zju\\o1108","w",stdout);
#endif

    int i,j,k,n=0,best,best_j;
    int mice[1000][3];
    int b[1000],from[1000],res[1000];

    while (scanf("%d%d\n",&mice[n][0],&mice[n][1])==2) {
        mice[n][2]=n; n++;
    }
    qsort(mice,n,12,cmp);
    b[0]=1; from[0]=-1;
    for (i=1;i<n;i++) {
        best=1; best_j=-1;
        for (j=0;j<i;j++) if 
((mice[j][0]<mice[i][0])&&(mice[j][1]>mice[i][1]))
            if (b[j]+1>best) {
                best=b[j]+1;
                best_j=j;
            }
        b[i]=best;
        from[i]=best_j;
    }
    k=0; for (i=1;i<n;i++) if (b[i]>b[k]) k=i;
    i=0;
    while (k!=-1) {
        res[i++]=k;
        k=from[k];
    }
    printf("%d\n",i);
    while (i) printf("%d\n",mice[res[--i]][2]+1);
}