dp，讲述一些经验和细节注意

解题思路:

注意事项:

参考代码:

#include<bits/stdc++.h>//最大上升子序列的问题，O(n^2)算法轻松解决

//这种题用不了O(nlogn)的二分算法，因为存在两个元素无法比较的现象，比如4*3和1*5的矩形就无法比较

using namespace std;

#define maxN 15

#define maxn 1010

#define fir first

#define sec second

int N,n;

int dp[maxn];//dp[i]是前i个元素组成的包含第i个元素的最长上升子序列的长度，显然答案

//必为一个dp[i]

int ans;

pair<int,int> rec[maxn];

bool cmp1(pair<int,int> &x,pair<int,int> &y){

    if(x.fir==y.fir)return x.sec<y.sec;

    return x.fir<y.fir;

}

bool cmp(pair<int,int> &x,pair<int,int> &y){//不能直接用这个函数作为sort()的比较函数，因为不是任意两个元素都可比

//比如4*3和1*5的矩形就无法比较，谁在前面都返回1，这样即使排序完成后，也不是每一对元素都符合x.fir<y.fir&&x.sec<y.sec

//最终无法过样例

//很难说清楚，但还是应该找每两个元素都可比的比较函数，比如cmp1

    return x.fir<y.fir&&x.sec<y.sec;

}

int main(){

    scanf("%d",&N);

    while(N--){

        scanf("%d",&n);

        ans=0;

        memset(dp,0,sizeof(dp));

        int x,y;

        rec[0].first=rec[0].second=0;

        for(int i=1;i<=n;i++){

            scanf("%d%d",&x,&y);

            rec[i].fir=max(x,y);

            rec[i].sec=min(x,y);

        }

        sort(rec+1,rec+1+n,cmp1);

        for(int i=1;i<=n;i++){

            for(int j=0;j<i;j++){

                if(cmp(rec[j],rec[i])){

                    dp[i]=max(dp[i],dp[j]+1);

                }

            }

            ans=max(ans,dp[i]);

        }

        printf("%d\n",ans);

    }

    //system("pause");

    return 0;

}