長方形ネストの単調増分サブシーケンスの解決

長方形のネスト
時間制限:
3000
ms|メモリ制限:
65535
 KB
難易度:
5
説明
長さと幅を表すn個の矩形があり、各矩形はa,bで記述することができる.矩形X(a,b)は、矩形Y(c,d)にネストすることができ、aのみ
入力
1行目は正の数Nである(0試験データのグループ毎の1行目は正の数nであり、このグループの試験データに矩形の個数が含まれていることを示す(n<=1000)
次のn行は、各行に2つの数a,b(0 しゅつりょくテストデータのセットごとに1つの数を出力し、最大条件を満たす矩形の数を表し、各グループの出力は1行を占めます。 サンプル入力 1 10 1 2 2 4 5 8 6 10 7 9 3 1 5 8 12 10 9 7 2 2 サンプル出力 5
 
#include #include #include #include using namespace std; struct rectMatrix { int a,b; }rMatrix[1005]; int trec[1005]; int rCompare(const void *r1,const void *r2) { return (*(struct rectMatrix *)r1).a-(*(struct rectMatrix *)r2).a; } int main() { int t,i,j,num,smax,temp;//freopen("E://input.txt","r",stdin); scanf("%d",&t); while(t--) { smax=0; scanf("%d",&num); memset(trec,0,sizeof(trec)); for (i=0;irMatrix[j].a&&rMatrix[i].b>rMatrix[j].b&&trec[j]+1>trec[i]) { trec[i]=trec[j]+1; if (trec[i]>smax) smax=trec[i]; } printf("%d/n",smax+1); } return 0; }