本来是个很水的DP，结果被自己的代码习惯给打败了
代码：
1 #include<iostream> 2 #include<stdlib.h> 3 #include<string.h> 4 5 using namespace std; 6 7 typedef struct rectangle 8 { 9 int x; 10 int 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 { 21 int &ans = d[t]; 22 if(ans>=0) 23 return ans; 24 int max=0; 25 for(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 } 33 return d[t] = max+1; 34 } 35 36 37 int main() 38 { 39 int T; 40 cin>>T; 41 while(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 } 67 return 0; 68 }
d[]用来实现记忆化搜索，记忆化搜索是这个题的关键，几乎所有的DP都需要记忆化搜索，记忆化搜索是个非常好的技巧。另外map的构建。