DAG上的动规嵌套矩形问题

OpenJudge - 1001:嵌套矩形问题
http://cdsdzx.openjudge.cn/practice/1001/

这是紫书里嵌套矩形问题的简化版

注意要将d数组初始化为0，如果初始化为1的话，在记忆化上会出错。

代码如下（核心代码来自紫书）

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
using namespace std;
const int N=1001;
int a[N],b[N],g[N][N],d[N],n,m,x,y,lans;
int dp(int i);
void print(int i);
int main()
{
    //freopen("in.txt","r",stdin);
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        cin>>x>>y;
        g[x][y]=1;
    }
    memset(d,0,sizeof(d));//<<endl;  //这道题里起点是确定的 
    cout<<dp(1)-1<<" ";
    print(1);
    return 0;
}
int dp(int i)
{
    if(d[i]>0)
    return d[i];
    int& ans=d[i];
    ans=1;
    for(int j=1;j<=n;j++)
       if(g[i][j]>0)
          ans=max(ans,dp(j)+1);
    return ans;
}
void print(int i)
{
    cout<<i;
    for(int j=1;j<=n;j++)
      if(g[i][j]&&d[i]==d[j]+1)
      {
          cout<<"->";
          print(j);
          break;
      }
}