HDU/HDOJ 1677 Nested Dolls 搜索

类似于求最长下降子序列的个数，此题可以用动态规划来解，不过我用简单的搜素来做，可惜超时，先上代码再优化。

[cpp]
#include
#include
#include
#include
#include
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 return a.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 {
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
memset(visit,0,sizeof(visit));
int cnt=0;
for(int i=0;i {
if(visit[i])continue;
int k=i;
for(int j=0;j {
if(visit[j])continue;
if(a[k].w visit[j]=1;
k=j;
}
}
cnt++;
visit[i]=1;
}
cout< }
return 0;
}

#include
#include
#include
#include
#include
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 return a.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 {
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
memset(visit,0,sizeof(visit));
int cnt=0;
for(int i=0;i {
if(visit[i])continue;
int k=i;
for(int j=0;j {
if(visit[j])continue;
if(a[k].w visit[j]=1;
k=j;
}
}
cnt++;
visit[i]=1;
}
cout< }
return 0;
}