nyoj 16 嵌套矩形（DAG上的动态规划）

矩形嵌套

1101 22 45 86 107 93 15 812 109 72 2样例输出
5
分析：矩形之间的“可嵌套”关系是一个典型的二元关系，二元关系可以用图来建模，这个矩形嵌套是有向无环图，换句话说，它是一个DAG模型，所求便是DAG上的最长路径。设d(i)表示从结点i出发的最长路长度，状态方程： d(i)=max{d(j)+1};
AC代码如下;
#include<cstdio>#include<cstring>#include<vector>#include<algorithm>using namespace std;const int maxn=1000+10;int g[maxn][maxn];int d[maxn];struct node{	int x,y;	node(int x=0,int y=0):x(x),y(y){}}; int n;vector<node>vec;void build(){  //构建图，用邻接矩阵保存在矩阵g中 	for(int i=0;i<n;i++){		for(int j=0;j<n;j++){			if(i!=j){				int a,b,c,d;				a=vec[i].x;b=vec[i].y;				c=vec[j].x;d=vec[j].y;				if(a<c&&b<d || b<c&&a<d)g[i][j]=1;			}		}	}}int dp(int i){	int& ans=d[i];	if(d[i]>0)return ans;	ans=1;	for(int j=0;j<n;j++)		if(g[i][j])ans=max(ans,dp(j)+1);	return ans;}int main(){ 	int N; 	scanf("%d",&N); 	while(N--){ 	   scanf("%d",&n); 	   for(int i=0;i<n;i++){ 	   	int x,y; 	   	scanf("%d%d",&x,&y); 	   	vec.push_back(node(x,y));		}		memset(g,0,sizeof(g));		memset(d,0,sizeof(d));		build();		for(int i=0;i<n;i++)dp(i);		sort(d,d+n);		PRintf("%d/n",d[n-1]);		vec.clear();	 }	return 0;}