1665. Вавилонская башня

Имеется бесконечное количество прямоугольных кирпичей размерами x_i × y_i × z_i, каждый из которых можно ставить на любую грань (размеры каких-то двух сторон будут размерами основания, размер третьей стороны – высотой).

Ваша задача написать программу, находящую максимальную высоту башни, которую можно построить из этих кирпичей. Один кирпич может быть поставлен на другой, если размеры основания верхнего кирпича строго меньше соответствующих размеров основания нижнего.

Вход. В первой строке записано количество типов кирпичей n (1 ≤ n ≤ 30), за которым следуют 3n целых чисел (n троек x_i y_i, z_i), описывающих размеры каждого типа кирпичей (1 ≤ x_i, y_i, z_i ≤ 65000).

Выход. Выведите одно число – максимальную высоту башни.

Входные данные	Выходные данные
2 6 8 10 5 5 5	21

РЕШЕНИЕ

динамическое программирование

Анализ алгоритма

Имеются n различных типов кирпичей, самих кирпичей каждого типа бесконечное множество. Пирамида может содержать кирпичи одного типа. Ставить одинаковые кирпичи друг на друга нельзя: обе стороны верхнего кирпича должны быть строго меньше соответствующих сторон нижнего кирпича. Каждый кирпич (x, y, z) можно вращать, поэтому вместе с ним будем рассматривать также кирпичи (y, z, x) и (z, x, y). Введем отношение f(a, b) частичного порядка, означающее что на кирпич a можно сверху поставить кирпич b. Отсортируем кирпичи согласно этого отношения.

Пусть dp[i] содержит максимальную высоту башни, которую можно сложить из первых i кирпичей при условии, что i-ый кирпич лежит на верху башни. Изначально положим dp[i] равным высоте i-го кирпича. Далее вычислим

dp[i] =,

где максимум берется по всем таким j, что на кирпич j можно поставить кирпич i. Ответом будет максимальное значение среди dp[i].

Реализация алгоритма

Опишем структуру кирпича, содержащую длину, ширину и высоту.

struct box

{

int x, y, z;

box (int x, int y, int z) : x(x), y(y), z(z) {}

};

Объявим входной массив кирпичей brick. Объявим дополнительный массив dp.

vector<box> brick;

vector<int> dp;

Функция f возвращает истину, если на кирпич a можно поставить кирпич b.

int f(box a, box b)

{

return (((a.x < b.x) && (a.y < b.y)) ||

((a.x < b.y) && (a.y < b.x)));

}

Основная часть программы. Читаем входные данные.

while(scanf("%d",&n), n)

{

N = 3*n;

dp.clear(); dp.resize(N);

brick.clear();

for(i = 0; i < n; i++)

{

scanf("%d %d %d",&a,&b,&c);

brick.push_back(box(a,b,c));

Поскольку кирпич (a, b, c) можно вращать, то вместе с ним рассматриваем также кирпичи (b, c, a) и (c, a, b).

brick.push_back(box(b,c,a));

brick.push_back(box(c,a,b));

}

Сортируем кирпичи согласно частичного порядка f. Функция сортировки STL при частичном порядке не работает.

for(i = 0; i < N; i++)

for(j = i + 1; j < N; j++)

if (f(brick[j],brick[i])) swap(brick[i],brick[j]);

Вычисляем значения массива dp:

for(res = -1, i = 0; i < N; i++)

{

Изначально устанавливаем значение dp[i] равным высоте i-го кирпича.

dp[i] = brick[i].z;

Перебираем все кирпичи j, на которые можно поставить i-ый. Если i-ый кирпич можно поставить на j-ый, то высота такой пирамиды составит dp[j] + brick[i].z.

for(j = 0; j < i; j++)

if(f(brick[j],brick[i]))

dp[i] = max(dp[i],dp[j] + brick[i].z);

res = max(res,dp[i]);

}

Выводим ответ.

printf("%d\n",res);

}