摸索C語言 前身 : 摸索C語言 http://mypaper.pchome.com.tw/iustlovefish 現在即將就讀中興大學資訊科學與工程學系 XD

79愛的鼓勵 1訂閱站台

作法:(1)DFS(測資小可以使用)(2)DP(LIS最長遞增子序列)
在此提供DFS

類似題:ACM 437 The Tower of Babylon (這題我採用DP 測資太大...)

/************************************************************/

#include<stdio.h>
#include<stdlib.h>
int n;
char map[50][50]={0};
int data[50][2]={0},flag[101]={0},max=0;
void DFS(int now,int many)
{
  if(many>max) max=many;
  int a;
  for(a=1;a<=n;a++)
   if(map[now][a]==1&&flag[a]==0)
    {
      flag[a]=1;
      DFS(a,many+1);
      flag[a]=0;
    }
}
main()
{
 int a,b,time=0;
 for(a=1;a<50;a++)
  map[0][a]=1;
 while(scanf("%d",&n)==1)
   {
     for(a=1;a<50;a++)
      for(b=1;b<50;b++)
        map[a][b]=0;
     for(a=1;a<=n;a++)   scanf("%d %d",&data[a][0],&data[a][1]);
     for(a=1;a<=n;a++)
       for(b=1;b<=n;b++)
           if((data[a][0]<=data[b][0]&&data[a][1]<=data[b][1])||(data[a][0]<=data[b][1]&&data[a][1]<=data[b][0]))
            { map[a][b]=1;}
      max=0;
      DFS(0,0);
      printf("%d\n",max);
   }
 return 0;
}
/*
4
2 6
3 2
5 1
4 7
*/