hdu3457(有向图的dp问题)
2024-09-01 10:51:02
同http://www.cnblogs.com/ziyi--caolu/p/3202511.html
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
struct node
{
int x1,y1,x2,y2;
}s[1100];
int dp[1100],vist[1100][1100],n;
int dfs(int num)
{
if(dp[num]>0)
return dp[num];
dp[num]=1;
for(int i=1;i<=n;i++)
{
if(vist[num][i])
{
int tmp=dfs(i)+1;
if(tmp>dp[num])
dp[num]=tmp;
}
}
return dp[num];
}
int main()
{
while(scanf("%d",&n)>0&&n)
{
for(int i=1;i<=n;i++)
{
int x1,y1,x2,y2;
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
s[i].x1=x1;
s[i].y1=y1;
s[i].x2=x2;
s[i].y2=y2;
}
memset(dp,0,sizeof(dp));
memset(vist,0,sizeof(vist));
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
{
if(s[i].x2<s[j].x1&&s[i].y2<s[j].y1)
vist[i][j]=1;
}
int maxx=0;
for(int i=1;i<=n;i++)
{
int tmp=dfs(i);
if(tmp>maxx)
maxx=tmp;
}
printf("%d\n",maxx);
}
return 0;
}
最新文章
- 在不损坏C盘的情况下为C盘扩容,适用于Win
- android 滚动的缓冲图片
- ASP.NET MVC SSO 单点登录设计与实现
- MFC 单文档 根据数据 绘图
- composer 安装使用
- Java内部类的访问规则
- Hibernate的Restrictions用法
- 关于web会话中的session过期时间的设置
- SAX方式解析XML文件实例
- [A Top-Down Approach][第一章 计算机网络和因特网]
- HttpWebRequest操作已超时
- vue+webpack项目实际工作中需要生成一个配置文件供生产环境使用
- JS的事件多次触发,只执行最后一次
- c/c++ 网络编程 陈硕老师视频理解之ttcp
- 利用工具将数据库中的表导出到word中
- sqlserver 查询重复数据
- Ubuntu12.04 内核树建立
- php 递归数据,三维数组转换二维
- [FJOI2014]最短路径树问题 长链剖分
- JS 汉字与Unicode码的相互转化
热门文章
- [Todo]很不错的Java面试题类型整理,要看
- Windows之权限讲解
- DWG/DGN格式导入Arcgis;转化为shp格式;更改地理坐标;导入Google Earth【转】
- java设计模式3--单例模式(Singleton)
- 这两天对OKR简单总结
- NPOI导出Excel时出现错误“Maximum column number is 255”
- iOS 线程操作库 PromiseKit
- 从零开始编写自己的C#框架(25)——网站部署 【转】
- openerp domain 規則
- 在MVC的cshtml视图页获取默认路由下的ID值的方法