Description
有n個矩形，每個矩形可以用a,b來描述，表示長和寬盒发。矩形X(a,b)可以嵌套在矩形Y(c,d)中當(dāng)且僅當(dāng)a<c,b<d或者b<c,a<d（相當(dāng)于旋轉(zhuǎn)X90度）蝶防。例如（1,5）可以嵌套在（6,2）內(nèi)印荔，但不能嵌套在（3,4）中嘿悬。你的任務(wù)是選出盡可能多的矩形排成一行，使得除最后一個外钢拧，每一個矩形都可以嵌套在下一個矩形內(nèi)份殿。
Input
第一行是一個正正數(shù)N(0<N<10)拾枣，表示測試數(shù)據(jù)組數(shù)忿磅，
每組測試數(shù)據(jù)的第一行是一個正正數(shù)n似扔，表示該組測試數(shù)據(jù)中含有矩形的個數(shù)(n<=1000)
隨后的n行，每行有兩個數(shù)a,b(0<a,b<100)偶器，表示矩形的長和寬
Output
每組測試數(shù)據(jù)都輸出一個數(shù)霎苗，表示最多符合條件的矩形數(shù)目，每組輸出占一行
Sample Input Copy
1
10
1 2
2 4
5 8
6 10
7 9
3 1
5 8
12 10
9 7
2 2
Sample Output Copy
5
思路
對于任意兩個矩形A锰瘸，B如果A嵌套在B內(nèi)港庄，那么B一定不會嵌套在A內(nèi)佩谣，所以如果將一個個矩形視為節(jié)點的話调鬓，那么矩形間的嵌套關(guān)系可以用一張有向無環(huán)圖表示居砖，故此題可以抽象成一個DAG最長路問題，數(shù)組dp[]的第 i 個元素dp[i]表示從第 i 個矩形開始所能嵌套的最多的矩形個數(shù)，故可以寫出如下狀態(tài)轉(zhuǎn)移方程：向楼。
代碼(C++)
#include <iostream>
#include <cmath>
#include <cstring>
#define MAXN 1005
using namespace std;
struct rect{
int l, w;
}rects[MAXN];
int dp[MAXN], n, T, res;
int DP(int i){
if(dp[i] > 0)return dp[i];
for(int j = 0; j < n; j++){
if((rects[i].l < rects[j].l && rects[i].w < rects[j].w) || (rects[i].l < rects[j].w && rects[i].w < rects[j].l)){
dp[i] = max(dp[i], DP(j) + 1);
if(dp[i] > res)res = dp[i];
}
}
return dp[i];
}
int main(){
scanf("%d", &T);
while(T--){
memset(dp, 0, sizeof(dp));
res = 0;
scanf("%d", &n);
for(int i = 0; i < n; i++){
scanf("%d%d", &rects[i].l, &rects[i].w);
}
DP(0);
printf("%d\n", res + 1);
}
return 0;
}
