Codeforces 4D Mysterious Present

http://codeforces.com/contest/4/problem/D

题目大意：

给出n个信封，这n个信封有长和宽，给出卡片的尺寸，求取能够装入卡片的最长的序列，序列满足后一个的长和宽一定大于前一个，求最长的这个序列的长度，并且给出一组可行解。

思路:最长上升子序列

#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<iostream>
int n,f[500005],from[500005];
int tot,c[500005];
struct node{
    int h,w,id;
}a[200005];
int read(){
    int t=0,f=1;char ch=getchar();
    while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
    while ('0'<=ch&&ch<='9'){t=t*10+ch-'0';ch=getchar();}
    return t*f;
}
bool operator <(node a,node b){
    return (a.h<b.h&&a.w<b.w);
}
bool cmp(node a,node b){
    if (a.h==b.h) return a.w<b.w;
    else return a.h<b.h;
}
int main(){
    n=read();n++;
    int cnt=0;
    for (int i=1;i<=n;i++){
        a[++cnt].h=read();a[cnt].w=read();
        a[cnt].id=i-1;
        if (i!=1&&(a[cnt].h<=a[1].h||a[cnt].w<=a[1].w)) cnt--;
    }
    n=cnt;
    std::sort(a+1,a+1+n,cmp);
    int ans=1,mx=1;
    f[1]=1;
    for (int i=2;i<=n;i++){
       for (int j=1;j<i;j++)
        if (f[i]<f[j]+1&&a[j]<a[i]&&f[j])
         from[i]=j,f[i]=f[j]+1;
       if (f[i]>ans) ans=f[i],mx=i;
    }
    if (ans==1) {printf("0");return 0;}
    int top=0;
    for (int i=mx;i!=1;i=from[i]){
        c[++top]=a[i].id;
    }
    printf("%d
",ans-1);
    for (int i=top;i>=1;i--)
     printf("%d ",c[i]);
     
}