codeup 11.6 DAG最長路 問題 A: 矩形嵌套

問題 A: 矩形嵌套

時間限制: 1 Sec  記憶體限制: 64 MB

送出: 198  解決: 92

[​​​送出​​​][​​狀态​​​][​​讨論版​​][命題人:外部導入]

題目描述

有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

#include<iostream>
#include <cstring>
using namespace std;

const int N=1010;
int G[N][N];
int dp[N];
int T,n;

struct Rect
{
  int x,y;
  bool operator <(Rect r){
    if(x<r.x&&y<r.y||x<r.y&&y<r.x) return true;
    return false;
  } 
}rect[N];

int DP(int i){
  if(dp[i]>0) return dp[i];
  for(int j=0;j<n;j++){
    if(G[i][j]!=0){
      int temp=DP(j)+G[i][j];//其實就是+1 此時就有兩個2
      if(temp>dp[i]){
        dp[i]=temp;
      }
    }
  }
  return dp[i];
}

int main(){
  // freopen("input1.txt","r",stdin);
  cin>>T;
  while(T--){
    memset(dp,0,sizeof(dp));
    memset(G,0,sizeof(G));
    cin>>n;
    for(int i=0;i<n;i++){
      cin>>rect[i].x>>rect[i].y;      
    }

    for(int i=0;i<n;i++){
      for(int j=0;j<n;j++)
        if(rect[i]<rect[j]){
          G[i][j]=1;
        }
    }

    int max=0;
    for(int i=0;i<n;i++){
      if(max<DP(i)) max=dp[i];
    }
    cout<<max+1<<endl;//max條邊 max+1個點
  }

  return 0;
}