链-反链-Dilworth定理

#include <iostream>#include <stdio.h>#include <string.h>#include <math.h>#include <algorithm>#include <string>#include <queue>#include <stdlib.h>using namespace std;#define N 5050struct node{    int x,y;}g[N];int cmp(node t,node t1){    return t.x<t1.x;}int dp[N];int main(){    int T;    scanf("%d",&T);    while(T--)    {        int n;        scanf("%d",&n);        for(int i=0;i<n;i++)            scanf("%d%d",&g[i].x,&g[i].y);        sort(g,g+n,cmp);        memset(dp,0,sizeof(dp));        dp[0]=1;        int ans=1;        for(int i=1;i<n;i++)        {            int tmp=0;            for(int j=0;j<i;j++)            {                if(g[j].x==g[i].x) continue;                if(g[j].y>g[i].y) tmp=max(tmp,dp[j]);            }            dp[i]=tmp+1;            ans=max(ans,dp[i]);        }        printf("%d\n",ans);    }    return 0;}