ACM 437 The Tower of Babylon
作法:(1)DFS(測資太大 TLE)(2)DP(LIS最長遞增子序列)
提供DP的想法:要先排序!!再做LIS
/*************************************************************/
#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;
}