1527. Торговцы картинами

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

· Цена картины, по которой она продается, должна быть не меньше цены, по которой она покупалась;

· Ни один продавец не может купить одну и ту же картину дважды.

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

Вход. Состоит из нескольких тестов, каждый из которых имеет следующую структуру. Первая строка содержит количество торговцев картин n (2 ≤ n ≤ 15). Каждая из следующих n строк содержит n цифр. Они описывают матрицу стоимостей, где j-ый символ i-ой строки содержит цифру – стоимость, за которую торговец j купит картину у торговца i. Известно, что 0 является наименьшей ценой, а 9 наибольшей.

Выход. Для каждого теста определите самую длинную последовательность перепродаж новой картины и выведите количество людей, которое ею владело, включая конечного владельца и торговца с номером 0. Ответы на каждый тест следует выводить с новой строки.

Пример входа	Пример выхода
2 01 10 3 022 101 110 5 01231 00231 00031 00002 00000	2 2 4

РЕШЕНИЕ

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

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

Состоянием будем называть тройку (mask, last, cost), обозначающую тот факт, что на данный момент владельцем картины является продавец с номером last, он заплатил за новую картину цену cost, а картиной не владели только те продавцы, на местах которых в mask стоят 0. Например, состояние (0010111₂, 2, 5) говорит о том, что второй продавец приобрел картину стоимостью 5, причем картиной еще не владели 3, 5 и 6 продавцы (крайняя справа единица в маске соответствует нулевому продавцу).

Начальное состояние имеет вид (1, 0, 0) – нулевой продавец приобрел картину за цену 0 и может продать ее любому из продавцов.

Функция solve(mask, last, cost) возвращает наибольшее количество продавцов, которые могут владеть новой картиной, если на данный момент продавец с номером last приобрел картину стоимостью cost, а продавать картину можно только тем продавцам, которым в маске mask соответствуют нули. Если текущий продавец никому продать картину не может, то наибольшая длина пути картины равна количеству единиц в двоичном коде числа mask.

Совершаем перебор всех возможных продаж с запоминанием всех состояний в массиве m.

Пример

Рассмотрим второй пример. Нулевой продавец может продать имеющуюся изначально у него картину или первому или второму продавцу за сумму 2. Таким образом при продаже первому продавцу мы переходим из начального состояния (1, 0, 0) в (11₂, 1, 2). Если нулевой продавец продаст картину второму продавцу, то переходим в состояние (101₂, 2, 2). В обоих случаях дальнейшая продажа картин не возможна: ни первый ни второй продавец не в состоянии перекупить картину ценой 2.

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

Значение функции solve(mask, last, cost) будем хранить в ячейке m[mask][last][cost] трехмерного массива m. Поскольку число торговцев не больше 15, то mask ≤ 2¹⁵ – 1 (максимальная маска состоит из 15 единиц), last < 15 (торговцы нумеруются числами от 0 до n – 1). Стоимость картины cost не больше 9.

Ячейка Price[i][j] содержит стоимость, за которую торговец j купит картину у торговца i.

int m[1<<15][15][10];

char Price[15][16];

Функция ones вычисляет количество единиц в бинарном представлении числа n.

int ones(int n)

{

int c = 0;

while(n) c++, n = n & (n - 1);

return c;

}

Реализация функции solve.

int solve(int mask, int last, int cost)

{

int temp, i, &ret = m[mask][last][cost];

Если значение m[mask][last][cost] уже вычислено (не нулевое), то возвращаем его.

if (ret) return ret;

Вычисляем количество продавцов, которые уже владели картиной (количество единиц в маске mask).

ret = ones(mask);

Перебираем имеющихся продавцов и смотрим, кому продавец с номером last может продать имеющуюся у него картину. Картину можно продать продавцу i, если i-ый бит маски mask равен нулю (у i-го продавца картина на руках еще не была), а также если продавец с номером i готов купить картину у продавца с номером last по цене, не меньшей cost (цене, по которой продавец last приобретал картину).

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

if(!(mask & 1<<i) && (Price[last][i] -'0') >= cost)

{

temp = solve(mask | 1 << i , i, Price[last][i] -'0');

if (temp > ret) ret = temp;

}

return ret;

}

Основная часть программы.

while(scanf("%d\n",&n) == 1)

{

memset(m,0,sizeof(m));

Продавцы нумеруются числами от 0 до n – 1.

for(i = 0; i < n; i++) gets(Price[i]);

res = solve(1,0,0);

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

}