记录编号	575606	评测结果	AAAAAAAAAA
题目名称	嵌套矩形	最终得分	100
用户昵称	┭┮﹏┭┮	是否通过	通过
代码语言	C++	运行时间	0.000 s
提交时间	2022-09-22 21:31:28	内存使用	0.00 MiB

#include <bits/stdc++.h> 
using namespace std;
const int N = 1010;
int n,f[N],nx[N];
vector<int>q[N];
struct made{
    int x,y,b;
}a[N];
bool cmp(made x,made y){
    if(x.x == y.x)return x.y < y.y;
    return x.x < y.x;
}
void init(){
    //输入，以宽为x，长为y 
    scanf("%d",&n);
    for(int i = 1;i <= n;i++){
        int x,y; 
        scanf("%d%d",&x,&y);
        a[i].x = min(x,y),a[i].y = max(x,y);
        a[i].b = i;
    } 
    //排序优化 
    sort(a+1,a+1+n,cmp);
}
int sou(int x,int s){
    //没有包括它的就返回 
    if(q[x].size() == 0){
        f[x] = 1; 
        return 1;
    }
    //ma为最大的长度，st为ma长度的初始下标 
    int ma = 1,st = x;
    //遍历每一条出边 
    for(int i = 0;i < q[x].size();i++){
        int ss = 0;
        if(f[q[x][i]])ss = f[q[x][i]]+1;//记忆化 
        else ss = sou(q[x][i],s+1)+1;
        //字典序 
        if(ss > ma){
            ma = ss;
            st = q[x][i];
        }
        else if(ss == ma && a[q[x][i]].b < a[st].b){
            st = q[x][i];
        }
    }
    nx[x] = st;//字典序 
    f[x] = ma;//记忆化 
    return ma;
}
void build() {
    //建图 
    for(int i = 1;i <= n;i++){
        for(int j = i+1;j <= n;j++){
            if(a[i].x < a[j].x && a[i].y < a[j].y) {
                q[i].push_back(j);
            }
        }
    }
}
void dfs(){
    //枚举每个初始包括点，倒序保证记忆化 
    //ma为最大的长度，st为ma长度的初始下标 
    int ma = 1,st = n;
    for(int i = n;i >= 1;i--){
        int ss = sou(i,1);
        //字典序 
        if(ss > ma){
            ma = ss;st = i;
        }
        else if(ss == ma && a[i].b < a[st].b){
            st = i;
        }
    }
    printf("%d\n",ma);
    //字典序，因为排序所以输出a[x].b,st存的是排序过后的下标，要转化为排序前下标 
    cout<<a[st].b;
    while(nx[st] != 0){
        cout<<' '<<a[nx[st]].b;
        st = nx[st];
    }
    printf("\n");
} 
int main(){
    freopen("qiantao.in","r",stdin);
    freopen("qiantao.out","w",stdout);
    init();
    build();
    dfs();
    
    return 0;
}