NYOJ 16 矩形嵌套 【dp DAG】

 1 #include<iostream>
 2 #include<algorithm>
 3 #include<cstdio>
 4 #include<cstring>
 5 using namespace std;
 6 #define clr(c) memset(c, 0, sizeof(c));
 7 
 8 const int MAXL = 1000+10;
 9 typedef struct{
10     int length;
11     int width;
12 }rectangle;
13 
14 rectangle R[MAXL]; // 矩形数组
15 bool G[MAXL][MAXL]; // DAG的邻接矩阵
16 int d[MAXL]; // 状态转移数组
17 int Case, n, num1, num2;
18 
19 void CreatGraph(){ // 建图
20     clr(G);
21     for(int i = 0; i < n; i++){
22         for(int j = 0; j < n; j++){
23             if(R[i].length < R[j].length && R[i].width < R[j].width){
24                 G[i][j] = true; // i 嵌套在 j 中
25             }
26         }
27     }
28 }
29 
30 int dp(int i){
31     int& ans = d[i]; // 引用
32     if(ans > 0) return ans;
33     ans = 1;
34     for(int j = 0; j < n; j++){
35         if(G[i][j]) ans = max(ans, dp(j)+1); // dp(j)从j出发的最长路径
36     }
37     return ans;
38 }
39 
40 int main(){
41     scanf("%d", &Case);
42     while(Case--){
43         scanf("%d", &n);
44         for(int i = 0; i < n; i++){ // 强行规定长 > 宽
45             scanf("%d%d", &num1, &num2);
46             R[i].length = max(num1, num2);
47             R[i].width = min(num1, num2);
48         }
49         CreatGraph();
50         clr(d); // 清空状态转移数组
51         int ans = 0;
52         for(int i = 0; i < n; i++){
53             int temp = dp(i);
54             ans = max(ans, temp); // 输出最大的结果
55         }
56         printf("%d\n", ans);
57     }
58 
59     return 0;
60 }