矩形嵌套

紫书P262 这是有向无环图DAG（Directed Acyclic Graph）上的动态规划，是DAG最长路问题

【题目类型】DAG上的dp

&题解：

矩形之间的"可嵌套"关系是一个典型的二元关系，二元关系可以用图来建模。如果矩形X可以嵌套在矩形Y里，我们就从X到Y连一条有向边。这个有向图是无环的，因为一个矩形无法直接或间接地嵌套在自己的内部。换句话说，它是一个DAG。这样，我们的任务便是求DAG上的最长路径。

紫书是这么说的，那么现在我们就已经将问题转化了，那我现在再说一下代码的问题：

int dp(int i){

	if (d[i]!=0) return d[i];

	d[i]=1;

	rep(j,n) if (G[i][j]) d[i]=max(d[i],dp(j)+1);

	return d[i];

}

这块，你要知道：函数dp求的是从i点到所以点的最远值，也就是说，假如你调用dp(3)他返回的是3到所有点的最远值。

所以你现在应该知道了，在调用dp的时候外面应该在套一层n的循环，代表每个点到终点的最远值，之后在循环中求最大值res，最后输出res就好了。

为什么dp(i)求的是从i点到各个点的最远值呢？

因为你传进去i，他第一步只会找到与i点连接的点，之后递归，第二步找到与i点连接的点的连接的点，之后继续递归……

所以他只会求出从i点到各个点的最远值。

但为什么又是最远的值呢？因为他每次都把d[i]更新，d[i]=max(d[i],dp(j)+1); 并且还返回d[i]，所以是最远的值。

这题还告诉我们，记忆化中的数组只是代表是否走过，他的值并没有什么特殊意义，我们需要的只是最后dp的返回值而已。

【时间复杂度】O(n^2)

&代码：

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

#define cle(a,val) memset(a,(val),sizeof(a))

#define SI(N) scanf("%d",&(N))

#define SII(N,M) scanf("%d %d",&(N),&(M))

#define rep(i,b) for(int i=0;i<(b);i++)

#define PI(A) cout<<(A)<<endl;

const int MAXN = 1000 + 5 ;

struct node{

	int x,y;

}a[MAXN];

int n,d[MAXN];

bool G[MAXN][MAXN];

int dp(int i){

	//remember

	if (d[i]!=0) return d[i];

	d[i]=1;

	rep(j,n) if (G[i][j]) d[i]=max(d[i],dp(j)+1);

	return d[i];

}

void Solve()

{

	SI(n);

	rep(i,n){

		SII(a[i].x,a[i].y);

		if(a[i].x<a[i].y) swap(a[i].x,a[i].y);

	}

	cle(G,0);

	rep(i,n) rep(j,n){

		if (i==j) continue;

		if (a[i].x<a[j].x&&a[i].y<a[j].y){

			G[i][j]=1;

		}

	}

	int res=0;

	rep(i,n){

		cle(d,0);

		int tm=dp(i);

		res=max(res,tm);

	}

	PI(res)

}

int main()

{

	int T;cin>>T;while(T--)

	Solve();

	return 0;

}

秒客网

NYOJ16 矩形嵌套（DAG最长路）

矩形嵌套

相关文章