动态规划 | DAG最长路

1.矩形嵌套

查了很久的错，最后发现是ans在每次测试样例输入的时候没有初始化为0 。

AC代码：

#include <stdio.h>
#include <memory.h>
#include <math.h>
#include <string>
#include <vector>
#include <set>
#include <stack>
#include <queue>
#include <algorithm>
#include <map>


#define I scanf
#define OL puts
#define O printf
#define F(a,b,c) for(a=b;a<c;a++)
#define FF(a,b) for(a=0;a<b;a++)
#define FG(a,b) for(a=b-1;a>=0;a--)
#define LEN 1010
#define MAX 1<<30
#define V vector<int>

using namespace std;

int dp[LEN];
int r[LEN];
int c[LEN];
int N,ans=0;
bool Greater(int a,int b){
    if((r[a]>r[b]&&c[a]>c[b])
    ||(c[a]>r[b]&&r[a]>c[b])) return 1;
    return 0;
}
int DP(int x){
    if(dp[x]>0) return dp[x];
    dp[x]=1;
    int i;
    FF(i,N){
        if(Greater(x,i)){    //顶点x到顶点y连通 
            dp[x]=max(dp[x],1+DP(i));
        }
    }
    ans=max(ans,dp[x]);
    return dp[x];
}

int main(){
//    freopen("矩形嵌套.txt","r",stdin);
    int i,j,T;
    I("%d",&T);
    while(T--){
        ans=0;
        memset(dp,0,sizeof dp);
        I("%d",&N);
        FF(i,N){
            I("%d%d",&r[i],&c[i]);
        }
        FF(i,N) DP(i);
        O("%d
",ans);
    }
    return 0;
}