#include<iostream> #include<algorithm> #include<cstring> using namespace std; struct node{ int h,w;
}rec[30000]; bool cmp(node a,node b){ if(a.h!=b.h) return a.h<b.h; else return a.w>b.w;
} int vis[30000]={0}; int n,count1; //void find(int k){ // if(k==n){return ;} // int ok=1; // for(int i=k+1;i<n;i++){ // if(!vis[i]&&rec[i].w>rec[k].w){ // vis[i]=1; // find(i); // ok=0; // break; // } // else find(i); // } // if(ok){ // count1++; // find(k+1); // } //} void find(int m){ int k; for( k=m+1;k<n;k++){ if(!vis[k]&&rec[k].w>rec[m].w&&rec[k].h>rec[m].h){ // cout<<"!!"<<endl; vis[k]=1;
            find(k); break;
        }
    } if(k>=n) { // cout<<m<<endl; count1++;}
} int main(){ int t;
    cin>>t; while(t--){
        cin>>n; for(int i=0;i<n;i++){ int h,w;
            scanf("%d%d",&h,&w);
            rec[i].h=h;
            rec[i].w=w;
        }
        count1=0;
        memset(vis,0,sizeof(vis));
        sort(rec,rec+n,cmp); for(int i=0;i<n;i++){ if(vis[i]) continue;
            find(i);}
        cout<<count1<<endl;
    }
}

矩形嵌套问题；

目前理解  贪心如此题，应该是h和w最为接近的两点想嵌套为局部最优解，而动态规划应为dijk类型f（x+1）=f（x） 这个f（x）包含了仅限于x以下的全局最优解   当然 也就是逆推可以求解