记录编号 |
241141 |
评测结果 |
AAAAAAAAAA |
题目名称 |
嵌套矩形 |
最终得分 |
100 |
用户昵称 |
liu_runda |
是否通过 |
通过 |
代码语言 |
C++ |
运行时间 |
0.034 s |
提交时间 |
2016-03-24 17:43:20 |
内存使用 |
1.27 MiB |
显示代码纯文本
#include<cstdio>
struct rec{
int l,w;
}data[1005];
bool m[1005][1005];//m[a][b]==true:rectangle a can be put inside b
bool inside(int a,int b){
return data[a].l<data[b].l&&data[a].w<data[b].w;
}
bool used[1005];
int next[1005];
int f[1005];
int ans=0,last=-1;
int n;
void search(int x){
used[x]=true;
f[x]=1;
for(int i=1;i<=n;++i){
if(m[i][x]){
if(!used[i])search(i);
if(f[i]+1>f[x]){
f[x]=f[i]+1;
next[x]=i;
}else if(f[i]+1==f[x]){
if(i<next[x])next[x]=i;
}
}
}
if(f[x]>ans){
ans=f[x];
last=x;
}else if(f[x]==ans){
if(x<last)last=x;
}
}
void printans(int x){
if(next[x]==0)printf("%d",x,data[x].w,data[x].l);
else{
printf("%d ",x,data[x].w,data[x].l);
printans(next[x]);
}
}
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",&data[i].l,&data[i].w);
if(data[i].l<data[i].w){
data[i].l^=data[i].w^=data[i].l^=data[i].w;
}
}
for(int i=1;i<=n;++i){
for(int j=1;j<=n;++j){
if(inside(j,i))m[i][j]=true;
// else if(inside(j,i))m[j][i]=true;
}
}
for(int i=1;i<=n;++i){
if(!used[i])search(i);
}
printf("%d\n",ans);
printans(last);
printf("\n");
fclose(stdin);fclose(stdout);
return 0;
}