描写叙述 有n个矩形，每个矩形能够用a,b来描写叙述，表示长和宽。
矩形X(a,b)能够嵌套在矩形Y(c,d)中当且仅当a<c,b<d或者b<c,a<d（相当于旋转X90度）。比如（1,5）能够嵌套在（6,2）内，但不能嵌套在（3,4）中。
你的任务是选出尽可能多的矩形排成一行。使得除最后一个外，每个矩形都能够嵌套在下一个矩形内。
- 输入
- 第一行是一个正正数N(0<N<10)，表示測试数据组数， 每组測试数据的第一行是一个正正数n。表示该组測试数据中含有矩形的个数(n<=1000) 随后的n行，每行有两个数a,b(0<a,b<100)，表示矩形的长和宽 输出
- 每组測试数据都输出一个数。表示最多符合条件的矩形数目。每组输出占一行 例子输入
-
1101 22 45 86 107 93 15 812 109 72 2
例子输出 -
5
-
-
思路：第一次打DAG上的动规。
实际上这个是一个有向图的最长路径问题，符合题目要求的用邻接表记录下来。表示能够由该节点走向下一个节点。之后就是考虑转移方程了。DP[i]=max(DP[i],dp(j)+1)。j为i出发的一个可行点。即从i可到达j。
-
以下给出AC代码（把路径打印的代码页附上）：
-
#include
#include #include using namespace std;#define N 1005int link[N][N]; //邻接表int u[N],v[N]; //各点的长跟宽int d[N]; //到达i的最长路径int n,m;int dp(int i) //记忆化搜索{ int& ans=d[i]; if(ans>0)return d[i]; ans=1; for(int j=1;j<=n;j++) { if(link[i][j]) ans=max(ans,dp(j)+1); } return ans;}void print(int i){ printf("%d ",i); for(int j=1;j<=n;j++) { if(link[i][j]&&d[i]==d[j]+1) { print(j); break; } } printf("\n");}int main(){ int i,j; int t; scanf("%d",&t); while(t--) { int ans=0; scanf("%d",&n); memset(link,0,sizeof(link)); for(i=1;i<=n;i++) { scanf("%d %d",&u[i],&v[i]); if(u[i]>v[i]) swap(u[i],v[i]); } for(i=1;i<=n;i++) { for(j=1;j<=n;j++) { if(u[i]