程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> 嵌套矩形 DAG上的dp（深搜+dp）

嵌套矩形 DAG上的dp（深搜+dp）

編輯：C++入門知識

矩形嵌套

時間限制：3000 ms | 內存限制：65535 KB 難度：4

描述

有n個矩形，每個矩形可以用a,b來描述，表示長和寬。矩形X(a,b)可以嵌套在矩形Y(c,d)中當且僅當a

輸入

第一行是一個正正數N(0 每組測試數據的第一行是一個正正數n，表示該組測試數據中含有矩形的個數(n<=1000)
隨後的n行，每行有兩個數a,b(0 輸出

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

樣例輸入

樣例輸出

來源

經典題目

上傳者

張雲聰

這題搞了好久，看白書上說的挺容易的，但是自己錯漏百出，把所以的缺點都暴露出來了，挺好！

剛開始用vector建圖直接TLE，剛開始沒看出來，然後才感覺出來，改成數組鄰接表2688ms，水過。用矩陣建圖反正才12ms，唉……題目中的圖正好是稠密圖，所以不管用vector還是數組鄰接表時間都很多也是這個原因，妹的！以前做圖論還沒遇到卡這的，現在終於遇到了。

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include
#include 
#include 
#define PI acos(-1.0)
#define mem(a,b) memset(a,b,sizeof(a))
#define sca(a) scanf(%d,&a)
#define sc(a,b) scanf(%d%d,&a,&b)
#define pri(a) printf(%d
,a)
#define lson i<<1,l,mid
#define rson i<<1|1,mid+1,r
#define MM 204
#define MN 1008
#define INF 2000000000
#define eps 1e-8
using namespace std;
typedef long long ll;
typedef unsigned long long ULL;
int n,dp[MN],head[MN*10],cnt;
struct node
{
    int x,y;
}e[MN];
struct no
{
    int v,next;
}ee[MN*10];
void add(int u,int v)
{
    ee[cnt].v=v,ee[cnt].next=head[u],head[u]=cnt++;
}
bool cmp(node a,node b)
{
    if(a.x==b.x) return a.yy) swap(x,y);
            e[i].x=x,e[i].y=y;
        }
        sort(e+1,e+n+1,cmp);
        for(i=1;i<=n;i++)
            for(j=i+1;j<=n;j++)
                if(e[i].x