本题为简单DP,需用单调递增子序列,不废话了一切尽在代码中。
代码:
#include<stdio.h> #include<algorithm> using namespace std; int dp[1005]; struct zhang { int x,y; }t[1005]; bool cmp(const zhang &a,const zhang &b) { return a.x < b.x ; } int main() { int T,i,j,max,a,b,n,q; scanf("%d",&T); while(T--) { scanf("%d",&n); max=0; for(i=0;i<n;i++) { scanf("%d%d",&a,&b); if(a>b) { q=a;a=b;b=q; } t[i].x=a;t[i].y=b; } sort(t,t+n,cmp); for(i=0;i<n;i++) { dp[i]=1; for(j=0;j<i;j++) if(t[i].x>t[j].x&&t[i].y>t[j].y&&dp[j]+1>dp[i]) dp[i]=dp[j]+1; if(max<dp[i]) max=dp[i]; } printf("%d\n",max); } return 0; }