Матч 430, Продавцы картин (ImageTraders)

Дивизион 2, Уровень 3

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

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

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

Некая новая картина появилась на рынке, и ее приобрел торговец с номером 0. Далее эта картина будет перепродаваться среди имеющихся любителей. Ячейка массива price[i][j] содержит цену, за которую i - ый торговец готов продать эту картину j - ому. Значение ‘0’ является наименьшей ценой, а ‘9’ – наибольшей. Необходимо определить наибольшее количество продавцов (включая 0 и последнего), которые могут владеть новой картиной.

Класс: ImageTraders

Метод: int maxOwners(vector<string> price)

Ограничения: price содержит в точности n элементов, 2 £ n £ 15, каждый элемент price содержит n символов ‘0’ – ‘9’.

Вход. Массив price содержит информацию о ценах продажи новой картины между продавцами.

Выход. Наибольшее количество продавцов (включая нулевого и последнего), которые могут владеть новой картиной.

Пример входа

price

{"01",

"10"}

{"022",

"101",

"110"}

{"01231",

"00231",

"00031",

"00002",

"00000"}

Пример выхода

2

2

4

РЕШЕНИЕ

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

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

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

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

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

ПРИМЕР

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

ПРОГРАММА

#include <cstdio>

#include <string>

#include <vector>

#include <memory>

using namespace std;

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

vector<string> P;

int ones(int n)

{

int c=0;

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

return c;

}

int solve(int mask, int last, int id)

{

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

if (ret) return ret;

ret = ones(mask);

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

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

{

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

if (temp > ret) ret = temp;

}

return ret;

}

class ImageTraders

{

public:

int maxOwners(vector<string> price)

{

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

P = price; n = (int)price.size();

return solve(1,0,0);

}

};