有向无环图上的动态规划是学习动态规划的基础，很多问题都可以转化为DAG上的最长路、最短路或路径计数问题。
嵌套矩阵
有n个矩阵，每个矩阵可以用两个整数a,b描述，表示它的长和宽。矩阵X(a,b)可以嵌套在矩阵Y(c,d)中当且仅当a<c,b<d，或者b<c,a<d（相当于把矩阵X旋转90。）例如(1,5)可以嵌套在(6,2)内，但不能嵌套在(3,4)内。你的任务是选出尽量多的矩阵排成一行，使得除了最后一个只之外，每一个矩形都可以嵌套在下一个矩形内。
分析：
矩阵之间的“可嵌套”关系是一个典型的二元关系，二元关系可以用图来建模。如果矩形X可以嵌套在矩形Y里，我们就从X到Y连一条有向边，这个图是无环的，因为一个矩形无法直接或者间接地嵌套在自己内部。换句话说，它是一个DAG，我们的任务便是求DAG上的最长路径。
设d(i)表示从结点i 出发的最长路长度。第一步只能到它的相邻点，d(i) = max{d(j)+1|(i,j)属于E}，其中E是边集。最终答案是所有d(i)中的最大值。假设用邻接矩阵保存在矩阵G中。
记忆化搜索代码如下：
1 #include<cstdio> 2 #include<cstdlib> 3 #include<cstring> 4 #include<algorithm> 5 #define maxn 1000 6 using namespace std; 7 int G[maxn][maxn], a[maxn], b[maxn], d[maxn], n, answer; 8 int dp(int i) 9 { 10 int& ans = d[i]; 11 if (ans > 0) return ans; 12 ans = 1; 13 for(int j = 1; j <= n; ++j) if(G[i][j]) ans = max(ans, dp(j)+1); 14 return ans; 15 } 16 void print_ans(int i) 17 { 18 printf("%d(%d, %d) ", i, a[i], b[i]); 19 for(int j = 1; j <= n; ++j) if(G[i][j] && d[j]+1 == d[i]) 20 { 21 print_ans(j); 22 break; 23 } 24 } 25 26 int path[maxn] = {0}, cnt = 0; 27 void print_all(int i) 28 { 29 //输出所有符合条件的路径 30 path[++cnt] = i; 31 if(cnt == answer) 32 { 33 for(int j = 1; j <= cnt; ++j) printf("%d(%d, %d) ", path[j], a[path[j]], b[path[j]]); 34 printf(" "); 35 } 36 else for(int j = 1; j <= n; ++j) if(G[i][j] && d[j]+1 == d[i]) 37 { 38 print_all(j); 39 } 40 --cnt; 41 } 42 /* 43 //作者的方法 44 int path[maxn]; 45 void print_all(int cur, int i) { 46 path[cur] = i; 47 if(d[i] == 1) { 48 for(int j = 0; j <= cur; j++) printf("%d ", path[j]); 49 printf(" "); 50 } 51 for(int j = 1; j <= n; j++) if(G[i][j] && d[i] == d[j]+1) 52 print_all(cur+1, j); 53 } 54 */ 55 int main() 56 { 57 freopen("9-2.in", "r", stdin); 58 scanf("%d", &n); 59 for(int i = 1; i <= n; ++i) scanf("%d%d", a+i, b+i); 60 memset(G, 0, sizeof(G)); 61 for(int i = 1; i <= n; ++i) 62 for(int j = 1; j <= n; ++j) if((a[i]>a[j]&&b[i]>b[j])||(a[i]>b[j]&&b[i]>a[j])) 63 G[i][j] = 1; 64 int t, s; 65 answer = -1; 66 memset(d, 0, sizeof(d)); 67 for (int i = 1; i <= n; ++i) 68 { 69 t = dp(i); 70 if(answer < t) 71 { 72 answer = t; 73 s = i; 74 } 75 } 76 printf("%d ", answer); 77 print_ans(s); 78 printf(" All routes: "); 79 //print_all(0, s); 80 print_all(s); 81 return 0; 82 }
另一代码如下：
1 //另附0ms 236kb的DP思路：按边长降序排序，用类似LIS的方法求解，只是比较元素大小的方法变成了比较长和宽 2 #include<cstdio> 3 #include<cstdlib> 4 #include<cstring> 5 #include<algorithm> 6 #define maxn 1008 7 using namespace std; 8 int G[maxn][maxn], a[maxn], b[maxn], d[maxn], n; 9 int dp(int i) 10 { 11 int& ans = d[i]; 12 if (ans > 0) return ans; 13 ans = 1; 14 for(int j = 1; j <= n; ++j) if(G[i][j]) ans = max(ans, dp(j)+1); 15 return ans; 16 } 17 int main() 18 { 19 int t; 20 scanf("%d", &t); 21 while(t--) 22 { 23 scanf("%d", &n); 24 for(int i = 1; i <= n; ++i) scanf("%d%d", a+i, b+i); 25 memset(G, 0, sizeof(G)); 26 for(int i = 1; i <= n; ++i) 27 for(int j = 1; j <= n; ++j) if((a[i]>a[j]&&b[i]>b[j])||(a[i]>b[j]&&b[i]>a[j])) 28 G[i][j] = 1; 29 int ans = -1, t, s; 30 memset(d, 0, sizeof(d)); 31 for (int i = 1; i <= n; ++i) 32 { 33 t = dp(i); 34 if(ans < t) 35 { 36 ans = t; 37 s = i; 38 } 39 } 40 printf("%d ", ans); 41 } 42 return 0; 43 }