java 嵌入式，南陽OJ 16 矩形嵌套

描寫敘述 有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)，表示矩形的長和寬

輸出

每組測試數據都輸出一個數。表示最多符合條件的矩形數目。每組輸出占一行

例子輸入

1
10
1 2
2 4
5 8
6 10
7 9
3 1
5 8
12 10
9 7
2 2

例子輸出

5

思路：第一次打DAG上的動規。

實際上這個是一個有向圖的最長路徑問題，符合題目要求的用鄰接表記錄下來。表示能夠由該節點走向下一個節點。之后就是考慮轉移方程了。DP[i]=max(DP[i],dp(j)+1)。j為i出發的一個可行點。即從i可到達j。

以下給出AC代碼（把路徑打印的代碼頁附上）：

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define N 1005
int 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]<u[j]&&v[i]<v[j]){link[i][j]=1;}}}int k;memset(d,0,sizeof(int)*(n+3));for(i=1;i<=n;i++)d[i]=dp(i);for(i=1;i<=n;i++){if(ans<d[i]){ans=d[i];k=i;}}printf("%d\n",ans);//print(k);}return 0;
}