UVA 437 The Tower of Babylon

5464 단어 uva
UVA_437
먼저 하나의 장방체를 3개로 바꾸어 저장한 다음에 바닥 면적의 크기에 따라 오름차순으로 배열하고 마지막으로 가장 긴 오름차순을 구하면 된다.
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define MAXD 110
int N, f[MAXD], a[5][MAXD], r[MAXD];
int cmp(const void *_p, const void *_q)
{
int *p = (int *)_p;
int *q = (int *)_q;
return a[0][*p] * a[1][*p] - a[0][*q] * a[1][*q];
}
int init()
{
int i;
scanf("%d", &N);
if(!N)
return 0;
N *= 3;
for(i = 0; i < N; i ++)
{
scanf("%d%d%d", &a[0][i], &a[1][i], &a[2][i]);
i ++;
a[2][i] = a[0][i - 1], a[0][i] = a[1][i - 1], a[1][i] = a[2][i - 1];
i ++;
a[2][i] = a[0][i - 1], a[0][i] = a[1][i - 1], a[1][i] = a[2][i - 1];
}
return 1;
}
void solve()
{
int i, j, ri, rj, temp, max;
for(i = 0; i < N; i ++)
r[i] = i;
qsort(r, N, sizeof(r[0]), cmp);
for(i = 0; i < N; i ++)
f[i] = a[2][r[i]];
for(i = 1; i < N; i ++)
{
ri = r[i];
for(j = 0; j < i; j ++)
{
rj = r[j];
if((a[0][rj] < a[0][ri] && a[1][rj] < a[1][ri]) || (a[0][rj] < a[1][ri] && a[1][rj] < a[0][ri]))
{
temp = f[j] + a[2][ri];
if(temp > f[i])
f[i] = temp;
}
}
}
max = 0;
for(i = 0; i < N; i ++)
if(f[i] > max)
max = f[i];
printf("%d
", max);
}
int main()
{
int t = 0;
while(init())
{
printf("Case %d: maximum height = ", ++ t);
solve();
}
return 0;
}

좋은 웹페이지 즐겨찾기