摘要：
这样，我们就可以来构建DAG图形，令，被包含的矩形a与包含的矩形b看成a一一˃b的路线，这样就形成了这样的图形：，我们一定知道最小矩形一定是不能包含其他矩形的，同时，知道最大矩形一定不能被包含。最小矩形和最大矩形是这整个dp的边界！同时，给出了dp的走势。
思路：
先把这些矩形统一 一下，让最长边向下，然后按大小放好。
这样，我们就可以来构建DAG图形， 令，被包含的矩形a与包含的矩形b看成a一一>b的路线，这样就形成了这样的图形：
，我们一定知道最小矩形一定是不能包含其他矩形的（因为没有矩形比最小矩形还小），同时，知道最大矩形一定不能被包含。（因为没有矩形比最大矩形大）
为什么，我们要考虑最大和最小矩形呢？
最小矩形和最大矩形是这整个dp的边界！同时，给出了dp的走势。
#include<iostream>#include<algorithm>#include<cstring> using namespacestd; const int maxn = 1e3 + 10; intdp[maxn], pre[maxn]; struct node{ intx, y; }a[maxn]; boolcmp(node a, node b){ if (a.x == b.x)return a.y <b.y; return a.x <b.x; } intn, x, y; intt; intmain(){ cin >>t; while (t--){ memset(dp, 0, sizeof(dp)); cin >>n; for (int i = 1; i <= n; ++i) { cin >> x >>y; if (x <y)swap(x, y); a[i].x = x; a[i].y =y; dp[i] = 1; } sort(a + 1, a + 1 +n, cmp); //for (int i = 1; i <= n; ++i) //cout << "(" << a[i].x << " ," << a[i].y << ")" << endl; for (int i = 1; i <= n - 1;++i) for (int j = i + 1; j <= n; ++j){ if (a[i].x < a[j].x&&a[i].y <a[j].y){ int sum = 1 +dp[i]; if (dp[j] < sum){ dp[j] = sum; pre[j] =i; } } } int maxx = 1; for (int i = 1; i <= n;++i) if (dp[maxx] < dp[i])maxx =i; //Path(maxx); cout << endl; cout << dp[maxx] <<endl; } }