P1375 嵌套矩形
2018-06-17 22:21:02来源:未知 阅读 ()
嵌套矩形
Time Limit: 1000ms Memory Limit: 131072KB有n个矩形,每个矩形可以用a,b来描述,表示长和宽。矩形X(a,b)可以嵌套在矩形Y(c,d)中当且仅当a<c,b<d或者b<c,a<d(相当于旋转X90度)。例如(1,5)可以嵌套在(6,2)内,但不能嵌套在(3,4)中。你的任务是选出尽可能多的矩形排成一行,使得除最后一个外,每一个矩形都可以嵌套在下一个矩形内
第2到n+1行每行两个数a,b,表示这个矩形的长和宽
输入数据
3 1 5 6 2 3 4
输出数据
2
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<cmath> 5 using namespace std; 6 const int MAXN=2001; 7 void read(int & n) 8 { 9 char c='+';int x=0;bool flag=0; 10 while(c<'0'||c>'9') 11 {c=getchar();if(c=='-')flag=1;} 12 while(c>='0'&&c<='9') 13 {x=x*10+(c-48);c=getchar();} 14 flag==1?n=-x:n=x; 15 } 16 int map[MAXN][MAXN]; 17 struct node 18 { 19 int hang; 20 int lie; 21 int id; 22 }a[MAXN*4]; 23 int ans=0; 24 int n; 25 int dis[MAXN]; 26 int M_s(int p) 27 { 28 ans=max(ans,dis[p]); 29 if(dis[p]) 30 return dis[p]; 31 for(int i=1;i<=n;i++) 32 { 33 if(map[p][i]) 34 return dis[p]=max(dis[p],M_s(i)+1); 35 } 36 } 37 int main() 38 { 39 read(n); 40 for(int i=1;i<=n;i++) 41 { 42 int x,y; 43 read(x);read(y); 44 a[i].hang=x;a[i].lie=y;a[i].id=i; 45 } 46 for(int i=1;i<=n;i++) 47 for(int j=1;j<=n;j++) 48 if(i!=j) 49 if((a[i].hang<a[j].hang&&a[i].lie<a[j].lie)||(a[i].lie<a[j].hang&&a[i].hang<a[j].lie)) 50 map[a[i].id][a[j].id]=1; 51 52 M_s(1); 53 int out=1; 54 for(int i=1;i<=n;i++) 55 { 56 out=max(out,dis[i]+1); 57 } 58 printf("%d",out); 59 return 0; 60 }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
上一篇:P1514 引水入城
下一篇:Tour UVA - 1347
- C++ 名称空间嵌套 2020-05-29
- [题记]有效括号的嵌套深度-leetcode 2020-04-01
- 洛谷P1034 矩形覆盖 2020-03-10
- POJ 1151 Atlantis 矩形面积求交/线段树扫描线 2019-04-18
- 最小包围矩形 2018-12-04
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash