动态规划：DAG-嵌套矩形

据说DAG是动态规划的基础，想一想还真的是这样的，动态规划的所有状态和转移都可以归约成DAG

DAG有两个典型模型，一个是嵌套矩形问题一个是硬币问题，这里仅介绍一个嵌套矩形问题

等二轮复习的时候再补上

NYOJ16，南阳OJ很不错的样子嘛

如果矩形X可以嵌套到矩形Y中，连有向边X->Y

求DAG的最长路径

这里起点和终点不用刻意给出，因为任意一个矩形都可以作为起点和终点

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 using namespace std;

 const int maxn=;

 int n;

 int a[maxn],b[maxn],d[maxn];

 int G[maxn][maxn];

 int dfs(int x)

 {

     if(d[x]>) return d[x];

     d[x]=;

     for(int i=;i<=n;i++)

         if(G[x][i]) d[x]=max(d[x],dfs(i)+);

     return d[x];

 }

 void print_ans(int x)

 {

     printf("%d ",x);

     for(int i=;i<=n;i++)

         if(G[x][i]&&d[x]==d[i]+)

         {

             print_ans(i);

             break;

         }

 }

 int main()

 {

     int T;

     scanf("%d",&T);

     while(T--)

     {

         memset(d,,sizeof(d));

         memset(a,,sizeof(a));

         memset(b,,sizeof(b));

         memset(G,,sizeof(G));

         scanf("%d",&n);

         for(int i=;i<=n;i++)

             scanf("%d%d",&a[i],&b[i]);

         for(int i=;i<=n;i++)

             for(int j=;j<=n;j++)

             {

                 if(a[i]>a[j]&&b[i]>b[j]||a[i]>b[j]&&b[i]>a[j])

                     G[i][j]=;

             }

         int tmp=;

         for(int i=;i<=n;i++)

             tmp=max(tmp,dfs(i));

         printf("%d\n",tmp);

     }

     return ;

 }

记忆化很舒适