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

79愛的鼓勵 1訂閱站台

作法:(1)DFS(測資太大 TLE)(2)DP(LIS最長遞增子序列)

提供DP的想法:要先排序!!再做LIS

類似題:95高市資訊學科能力競賽 矩形旋轉

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

#include<stdio.h>
#include<stdlib.h>   
int data[100][3]={0},max=0;
int LIS(int n)     
{     
 int i,j;  
 int array[100]={0};
    for(i=1;i<=n;i++) array[i]=data[i][2];     
    for(i=1;i<=n;i++)     
        for(j=i+1;j<=n;j++)
            if((data[j][0]<data[i][0]&&data[j][1]<data[i][1])||(data[j][0]<data[i][1]&&data[j][1]<data[i][0]))  
                array[j]=(array[j]>array[i]+data[j][2])?array[j]:(array[i]+data[j][2]);        
    int ans=0;     
    for(i=1;i<=n;i++)     
        ans=(ans>array[i])?ans:array[i];       
    return ans;  
}    
main()
{
 int n;
 int a,b,c,time=0;
 while(scanf("%d",&n)==1&&n!=0)
   {
     for(a=1;a<=n;a++)  
      {
       int nn,mm,oo;
       scanf("%d %d %d",&nn,&mm,&oo);
       data[a][0]=nn;data[a][1]=mm;data[a][2]=oo;
       data[n+a][0]=mm;data[n+a][1]=oo;data[n+a][2]=nn;
       data[2*n+a][0]=oo;data[2*n+a][1]=nn;data[2*n+a][2]=mm;
      }
     for(a=1;a<=3*n;a++)
      {
        c=a;
        for(b=a+1;b<=3*n;b++)
         if((data[c][0]<data[b][0]&&data[c][1]<data[b][1])||(data[c][0]<data[b][1]&&data[c][1]<data[b][0])) c=b;
        for(b=0;b<3;b++)
         {
           int temp;
           temp=data[c][b];
           data[c][b]=data[a][b];
           data[a][b]=temp;
         }
      }
      max=LIS(n*3);
      printf("Case %d: maximum height = %d\n",++time,max);
   }
 return 0;
}

/************ DFS 看看就好 *****************/

#include<stdio.h>
#include<stdlib.h>
int n;
char map[100][100]={0};
int data[100][2]={0},flag[100]={0},max=0;
int high[100]={0};
void DFS(int now,int H) /*now為點 H是高*/
{
/*  printf("%2d %2d\n",now,H); */
  if(H>max) max=H;
  int a;
  for(a=1;a<=3*n;a++)
     if(map[now][a]==1&&flag[a]==0)
      {
        flag[a]=1;
       /* printf("DFS深入 ->%2d\n",a); */
        DFS(a,H+high[a]);
       /* printf("退回\n"); */
        flag[a]=0;
      }
}
main()
{
 int a,b,c,time=0;
 for(a=0;a<100;a++)/*起點的關係建立*/
   map[0][a]=1;
 while(scanf("%d",&n)==1&&n!=0)
   {
     for(a=1;a<100;a++)
      {
       for(b=1;b<100;b++)
          map[a][b]=0;
          data[a][0]=0;
          data[a][1]=0;
          high[a]=0;
      }   
     for(a=1;a<=n;a++)  
      {
       int nn,mm,oo;
       scanf("%d %d %d",&nn,&mm,&oo);
       data[a][0]=nn;data[a][1]=mm;high[a]=oo;
       data[n+a][0]=mm;data[n+a][1]=oo;high[n+a]=nn;
       data[2*n+a][0]=oo;data[2*n+a][1]=nn;high[2*n+a]=mm;
      } 
      for(a=1;a<=3*n;a++)/*建出關係圖*/
       for(b=1;b<=3*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("Case %d: maximum height = %d\n",++time,max);
   }
 return 0;
}