HDU/HDOJ 1677 Nested Dolls 搜索

類似於求最長下降子序列的個數，此題可以用動態規劃來解，不過我用簡單的搜素來做，可惜超時，先上代碼再優化。

[cpp] 
#include <iostream>  
#include <cmath>  
#include <string>  
#include <algorithm>  
#include <vector>  
using namespace std; 
struct node{ 
    int w,h; 
}; 
node a[20001]; 
bool cmp(node a,node b){ 
    if(a.w!=b.w)return a.w<b.w; 
    return a.h<b.h; 
} 
bool visit[20001]; 
int main() 
{ 
    int t; 
    scanf("%d",&t); 
    //cin>>t;  
    while(t--) 
    { 
        int m; 
        scanf("%d",&m); 
        //cin>>m;  
        for(int i=0;i<m;i++) 
        { 
            scanf("%d %d",&a[i].w,&a[i].h); 
            //cin>>a[i].w>>a[i].h;  
        } 
        sort(a,a+m,cmp); 
        for(int i=0;i<m;i++)cout<<a[i].w<<" "<<a[i].h<<endl; 
         
        memset(visit,0,sizeof(visit)); 
        int cnt=0; 
        for(int i=0;i<m;i++) 
        { 
            if(visit[i])continue; 
            int k=i; 
            for(int j=0;j<m;j++) 
            { 
                if(visit[j])continue; 
                if(a[k].w<a[j].w&&a[k].h<a[j].h){ 
                    visit[j]=1; 
                    k=j; 
                } 
            } 
            cnt++; 
            visit[i]=1; 
        } 
        cout<<cnt<<endl; 
    } 
    return 0; 
} 

#include <iostream>
#include <cmath>
#include <string>
#include <algorithm>
#include <vector>
using namespace std;
struct node{
 int w,h;
};
node a[20001];
bool cmp(node a,node b){
 if(a.w!=b.w)return a.w<b.w;
 return a.h<b.h;
}
bool visit[20001];
int main()
{
 int t;
 scanf("%d",&t);
 //cin>>t;
 while(t--)
 {
  int m;
  scanf("%d",&m);
  //cin>>m;
  for(int i=0;i<m;i++)
  {
   scanf("%d %d",&a[i].w,&a[i].h);
   //cin>>a[i].w>>a[i].h;
  }
  sort(a,a+m,cmp);
  for(int i=0;i<m;i++)cout<<a[i].w<<" "<<a[i].h<<endl;
  
  memset(visit,0,sizeof(visit));
  int cnt=0;
  for(int i=0;i<m;i++)
  {
   if(visit[i])continue;
   int k=i;
   for(int j=0;j<m;j++)
   {
    if(visit[j])continue;
    if(a[k].w<a[j].w&&a[k].h<a[j].h){
     visit[j]=1;
     k=j;
    }
   }
   cnt++;
   visit[i]=1;
  }
  cout<<cnt<<endl;
 }
 return 0;
}