题目分析:矩形嵌套,很水的DP,先按长(宽)递增排序,再按宽(长)二级排序,类似最长上升子序列,
dp[i]=max(dp[j])+1; 1<=j<i;
原题链接:http://acm.nyist.net/JudgeOnline/problem.php?pid=16
#include<iostream> #include<cstdio> #include<algorithm> using namespace std; struct node{ int a,b; }arr[1200]; int dp[1200]; int cmp(node x,node y) { if(x.a==y.a) return x.b<y.b; else return x.a<y.a; } int main() { int t; scanf("%d",&t); while(t--) { int n,x,y; scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%d %d",&x,&y); if(x>y) { int temp=x; x=y; y=temp; } arr[i].a=x; arr[i].b=y; } sort(arr+1,arr+1+n,cmp); /*for(int i=1;i<=n;i++) printf("%d %d\n",arr[i].a,arr[i].b);*/ dp[1]=1; for(int i=2;i<=n;i++) { int ans=0; for(int j=1;j<i;j++) { if(arr[i].a!=arr[j].a && arr[i].b>arr[j].b&&dp[j]>ans) ans=dp[j]; } dp[i]=ans+1; } int ans=0; /*for(int i=1;i<=n;i++) printf("%d ",dp[i]);*/ //printf("\n"); for(int i=1;i<=n;i++) if(dp[i]>ans) ans=dp[i]; printf("%d\n",ans); } //system("pause"); return 0; }