来源：刘汝佳《算法竞赛入门经典--训练指南》 P60 问题2：
问题描述：有n个矩形，每个矩形可以用两个整数a,b描述，表示它们的长和宽。矩形X(a,b)可以嵌套在矩形Y(c,d)中的条件为：当且仅当a<c,b<d 或者b<c,a<d(相当于把矩形X旋转90 度)。选出尽量多的矩形排成一行，使得除了最后一个之外，每一个矩形都可以嵌套在下一个矩形内。
分析：对于本题中的n个矩形，以每个矩形作为一个点，若X矩形能嵌套在Y矩形中，则从X向Y连一条边，题目则变为了在DAG(无回路有向图)中求最长路径的问题。对每一个矩形i,设d(i)为矩形i结尾的最长链的长度，则d(i)=Max{0,d(j)|(矩形j可以嵌套在矩形i中)}+1;
例题来源：http://acm.nyist.net/JudgeOnline/problem.php?pid=16
代码实现：
#include "stdio.h"
#include "string.h"
#define N 1005 int n;
int dp[N];
int map[N][N]; struct point
{
int x,y;
}a[N]; int inline Max(int a,int b){ return a>b?a:b; } int Pudge(int a,int b,int c,int d)
{
if( (a<c&&b<d) || (b<c&&a<d) )
return ;
return ;
} int DFS(int k)
{
if(dp[k]!=-)
return dp[k];
int i;
dp[k] = ;
for(i=; i<n; i++)
{
if(map[i][k]==)
dp[k] = Max(dp[k],DFS(i)+);
}
return dp[k];
} int main()
{
int T;
int i,j;
int ans;
scanf("%d",&T);
while(T--)
{
ans = ;
scanf("%d",&n);
for(i=; i<n; i++)
scanf("%d %d",&a[i].x,&a[i].y);
memset(map,,sizeof(map));
for(i=; i<n; i++)
{
for(j=; j<n; j++)
{
if(i==j) continue;
if(Pudge(a[i].x,a[i].y,a[j].x,a[j].y))
map[i][j] = ;
}
}
memset(dp,-,sizeof(dp));
for(i=; i<n; i++)
ans = Max(ans,DFS(i));
printf("%d\n",ans);
}
return ;
}