题目链接:http://poj.org/problem?id=1065
题目分类:动态规划
代码:
#include<stdio.h> #include<string.h> #include<math.h> #include<algorithm> #include<iostream> using namespace std; #define INF 0x3f3f3f3f int n; int visit[5050]; struct P { int l,w; }a[5050]; int cmp(P X,P Y) { if(X.l==Y.l) return X.w<Y.w; return X.l<Y.l; } int main() { int t; scanf("%d",&t); while(t--) { memset(a,0,sizeof(a)); scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%d %d",&a[i].l,&a[i].w); } memset(visit,0,sizeof(visit)); sort(a+1,a+n+1,cmp); int ans=0; for(int i=1;i<=n;i++) { if(!visit[i]) { //printf("jhhh %d ",i); visit[i]=1; int temp=a[i].w; for(int j=i+1;j<=n;j++) { if(a[j].w>=temp&&!visit[j]) { temp=a[j].w; visit[j]=1; } } ans++; } } printf("%d ",ans); } return 0; }