本来是个很水的DP，结果被自己的代码习惯给打败了
代码：
1 #include<iostream> 2 #include<stdlib.h> 3 #include<string.h> 4 5 using namespace std; 6 7 typedef struct rectangle 8 { 9int x;10int y;11 }Rectangle;12 13 Rectangle a[1002];14 int map[1002][1002];15 int d[1002];16 int N;17 18 19 int dp(int t)20 {21int &ans = d[t];22if(ans>=0)23 return ans;24int max=0;25for(int i=0; i<N;i++)26{27 if(map[t][i]==1)28 {29 if(max<dp(i))30 max = dp(i);31 }32}33return d[t] = max+1;34 }35 36 37 int main()38 {39int T;40cin>>T;41while(T--)42{43 memset(d,-1,sizeof(d));44 cin>>N;45 for(int i=0; i<N;i++)46 {47 cin>>a[i].x>>a[i].y;48 }49 //构图50 memset(map,0,sizeof(map));51 for(int i=0; i<N; i++)52 {53 for(int j=0; j<N; j++)54 {55 if((a[i].x>a[j].x&&a[i].y>a[j].y)||(a[i].y>a[j].x&&a[i].x>a[j].y))56 map[i][j]=1;57 }58 }59 int max=0;60 for(int i=0; i<N; i++)61 {62 if(dp(i)>max)63 max = dp(i);64 }65 cout<<max<<endl;66}67return 0;68 }
d[]用来实现记忆化搜索，记忆化搜索是这个题的关键，几乎所有的DP都需要记忆化搜索，记忆化搜索是个非常好的技巧。另外map的构建。
