记录编号	47440	评测结果	AAAAAAAAAA
题目名称	嵌套矩形	最终得分	100
用户昵称	王者自由	是否通过	通过
代码语言	C++	运行时间	0.045 s
提交时间	2012-11-01 16:35:55	内存使用	2.65 MiB

#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 1000 + 10;
int n, k, s;
int a[N], b[N], f[N];
bool G[N][N];
int DP(int i) {
    if(f[i]) return f[i];
    f[i] = 1;
    for(int j=1; j<=n; j++)
        if(G[i][j])
            f[i] = max(f[i], DP(j) + 1);
    return f[i];
}
void print(int i) {
    printf("%d ", i);
    for(int j=1; j<=n; j++)
        if(G[i][j] && f[i] == f[j] + 1) {
            print(j);
            break;
        }
}
int main() {
    freopen("qiantao.in", "r", stdin);
    freopen("qiantao.out", "w", stdout);
    scanf("%d", &n);
    for(int i=1; i<=n; i++) {
        scanf("%d %d", a+i, b+i);
        if(a[i] > b[i]) swap(a[i], b[i]);
    }
    for(int i=1; i<=n; i++)
        for(int j=1; j<=n; j++)
            if(a[i] < a[j] && b[i] < b[j])
                G[i][j] = 1;
    for(int i=1; i<=n; i++)
        if(DP(i) > s)
            s = f[k = i];
    printf("%d\n", s);
    print(k);
    return 0; 
}