记录编号	595640	评测结果	AAAAAAAAAA
题目名称	嵌套矩形	最终得分	100
用户昵称	qyd	是否通过	通过
代码语言	C++	运行时间	0.114 s
提交时间	2024-10-15 16:30:59	内存使用	7.25 MiB

#include<bits/stdc++.h>
using namespace std;
const int maxn=1010;
int n;
int d[maxn];
struct matrix{
	int x,y;
}a[maxn];
int d_edge[maxn][maxn];
void build(int u,int v){
	if((a[u].x>a[v].x&&a[u].y>a[v].y)||(a[u].x>a[v].y&&a[u].y>a[v].x)){d_edge[v][u]=1;return ;}
	//which means u can cover v;
	if((a[u].x<a[v].x&&a[u].y<a[v].y)||(a[u].x<a[v].y&&a[u].y<a[v].x)){d_edge[u][v]=1;return ;}
	//which means u could be covered by v;
	return ;
}
int dp(int i){
	int &ans=d[i];
	if(ans>0)return ans;
	ans=1;
	for(int j=1;j<=n;j++)
	  if(d_edge[i][j])
	    ans=max(ans,dp(j)+1);
	return ans;
}
void print_ans(int i){
	cout<<i<<" ";
	for(int j=1;j<=n;j++)
	  if(d_edge[i][j]&&d[i]==d[j]+1)
	    {print_ans(j);break;}
}
int main()
{
	freopen("qiantao.in","r",stdin);
	freopen("qiantao.out","w",stdout);
	cin>>n;
	memset(d,0,sizeof(d));
	memset(d_edge,0,sizeof(d_edge));
	for(int i=1;i<=n;i++)
	{
		cin>>a[i].x>>a[i].y;
		for(int j=1;j<i;j++)
		  build(i,j);
	}
	int maxd=-1,id;
	for(int i=1;i<=n;i++)
	{
		d[i]=dp(i);
		if(d[i]>maxd)
		{
			maxd=d[i];
			id=i;
		}
	}
	cout<<maxd<<endl;
	print_ans(id);
	return 0;	
}