矩形嵌套
描述
有n个矩形,每个矩形可以用a,b来描述,表示长和宽。矩形X(a,b)可以嵌套在矩形Y(c,d)中当且仅当a
输入
第一行是一个正正数N(0 每组测试数据的第一行是一个正正数n,表示该组测试数据中含有矩形的个数(n<=1000)
随后的n行,每行有两个数a,b(0 输出
每组测试数据都输出一个数,表示最多符合条件的矩形数目,每组输出占一行
样例输入
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 using namespace std; struct space { int a; int b; }c[1005]; bool cmp(space _x,space _y)//必须排序 { if(_x.a==_y.a) return _x.b<_y.b; else return _x.a<_y.a; } int main() { int N,n,p,q,i,j,dp[1005]; scanf("%d",&N); while(N--) { memset(dp,0,sizeof(dp)); scanf("%d",&n); for(i=0;iq?p:q; c[i].b=pdp[i]) dp[i]=dp[j]+1; } if(k