NYOJ16 矩形嵌套 —

NYOJ16 矩形嵌套 ——DP入门题

题目链接：http://acm.nyist.net/JudgeOnline/problem.php?pid=16

题目大意：

　　中文题……

题目思路：

方法一：

　　先按照长和宽进行二级排序，然后转化成最长上升子序列求解。时间复杂度O(N^2)，数据范围1000.

 1 #include <iostream>
 2 #include <algorithm>
 3 #include <cstdio>
 4 #include <cstdlib>
 5 #include <cstring>
 6 #include <cstring>
 7 using namespace std;
 8 const int MAX = 1000+10;
 9 typedef struct node {
10   int x, y;
11   bool operator < (const node &other) const {
12     if (x != other.x) {
13       return x < other.x;
14     } else return y < other.y;
15   }
16 }node;
17 node ma[MAX];
18 int n, maxlen[MAX];
19 void init() {
20   int i, a, b;
21   scanf("%d", &n);
22   for (i = 0; i < n; ++i) {
23     scanf("%d%d", &a, &b);
24     if (a > b) swap(a,b);
25     ma[i].x = a; ma[i].y = b;
26   }
27   memset(maxlen, 0, sizeof(maxlen));
28   maxlen[0] = 1;
29 }
30 bool judge(node a, node b) {
31   if ((a.x<b.x && a.y<b.y) || (a.y<b.x && a.x<b.y)) return true;
32   else return false;
33 }
34 void solve() {
35   int i, j, tmp(0);
36   sort(ma, ma+n);
37   for (i = 1; i < n; ++i) {
38     tmp = 0;
39     for (j = 0; j < i; ++j) {
40       if (judge(ma[j], ma[i])) {
41         tmp = max(tmp, maxlen[j]);
42       }
43     }
44     maxlen[i] = tmp + 1;
45   }
46   tmp = 0;
47   for (i = 0; i < n; ++i) {
48     tmp = max(tmp, maxlen[i]);
49   }
50   printf("%d\n", tmp);
51 }
52 int main(void) {
53   int t; scanf("%d", &t);
54   while (t--) {
55     init();
56     solve();
57   }
58   return 0;
59 }

其实这是很自然的思路

方法二：

　　如果一个矩形可以嵌套进另一个矩形中，那么就建一条矩形边。那么转化成有向无环图的最长路。d(i)表示从节点i出发的最长路的长度。

有：d(i) = max(d(i), d(j)+1| G[i][j]==1 )

　　然后就是所谓的记忆化搜索……

　　程序35行里面用了一个技巧，声明了一个引用，可以直接改变原来的变量的值，比较方便。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstdlib>
 4 #include <cstring>
 5 #include <algorithm>
 6 using namespace std;
 7 const int MAX = 1000+10;
 8 int n;
 9 typedef struct node{
10   int x, y;
11 }node;
12 node ma[MAX];
13 int G[MAX][MAX], d[MAX];
14 bool judge(node a, node b) {
15   if ((a.x<b.x && a.y<b.y) || (a.y<b.x && a.x<b.y)) return true;
16   else return false;
17 }
18 void init() {
19   int i, j, a, b;
20   scanf("%d", &n);
21   memset(G, 0, sizeof(G));
22   memset(d, 0, sizeof(d));
23   for  (i = 0; i < n; ++i) {
24     scanf("%d%d", &a, &b);
25     if (a > b) swap(a, b);
26     ma[i].x = a; ma[i].y = b;
27   }
28   for (i = 0; i < n; ++i) {
29     for (j = 0; j <n; ++j) {
30       if (judge(ma[i], ma[j])) G[i][j] = 1;
31     }
32   }
33 }
34 int dp(int i) {
35   int &ans = d[i];
36   int j;
37   if (ans > 0) return ans;
38   ans = 1;
39   for (j = 0; j < n; ++j) {
40     if (G[i][j]) ans = max(ans, dp(j) + 1);
41   }
42   return ans;
43 }
44 void solve() {
45   int i, ans = 0;
46   for (i = 0; i < n; ++i) {
47     d[i] = dp(i);
48   }
49   for (i = 0; i < n; ++i) {
50     ans = max(ans, d[i]);
51   }
52   printf("%d\n", ans);
53 }
54 int main(void) {
55   int t; 
56   scanf("%d", &t);
57   while (t--) {
58     init();
59     solve();
60   }
61   return 0;
62 }

效率比方法一低

这个题目如果需要按照字典序打印出最终选择的矩形的编号，并且要求字典序最小，那么应该加上一个print_ans()函数，如下：

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstdlib>
 4 #include <cstring>
 5 #include <algorithm>
 6 using namespace std;
 7 const int MAX = 1000+10;
 8 int n;
 9 typedef struct node{
10   int x, y;
11 }node;
12 node ma[MAX];
13 int G[MAX][MAX], d[MAX];
14 bool judge(node a, node b) {
15   if ((a.x<b.x && a.y<b.y) || (a.y<b.x && a.x<b.y)) return true;
16   else return false;
17 }
18 void init() {
19   int i, j, a, b;
20   scanf("%d", &n);
21   memset(G, 0, sizeof(G));
22   memset(d, 0, sizeof(d));
23   for  (i = 0; i < n; ++i) {
24     scanf("%d%d", &a, &b);
25     if (a > b) swap(a, b);
26     ma[i].x = a; ma[i].y = b;
27   }
28   for (i = 0; i < n; ++i) {
29     for (j = 0; j <n; ++j) {
30       if (judge(ma[i], ma[j])) G[i][j] = 1;
31     }
32   }
33 }
34 int dp(int i) {
35   int &ans = d[i];
36   int j;
37   if (ans > 0) return ans;
38   ans = 1;
39   for (j = 0; j < n; ++j) {
40     if (G[i][j]) ans = max(ans, dp(j) + 1);
41   }
42   return ans;
43 }
44 void print_ans(int i)  {
45   printf("%d ", i);
46   int j;
47   for (j = 0; j < n; ++j) {
48     if (G[i][j] == 1 && d[i] == d[j] + 1) {
49       print_ans(j); break;
50     }
51   }
52 }
53 void solve() {
54   int i, ans = 0, index = 0;
55   for (i = 0; i < n; ++i) {
56     d[i] = dp(i);
57   }
58   for (i = 0; i < n; ++i) {
59     if (ans < d[i]) {
60       ans = d[i]; index = i;
61     }
62   }
63   printf("%d\n", ans);
64   print_ans(index);
65   printf("\b\n");
66 }
67 int main(void) {
68   int t; 
69   freopen("16.in", "r", stdin);
70   scanf("%d", &t);
71   while (t--) {
72     init();
73     solve();
74   }
75   return 0;
76 }

打印的思路就是从头开始，一次找下一个序号最小的点，同时满足最终的d[]数组之间关系的点。printf()里面有一个\b是为了不输出多余的空格，这个转义字符的作用是退格。