There is a community of art lovers who meet
from time to time and trade images with each other. Each image transaction must
obey the following rules:
·
The
price at which the image is sold must be greater than or equal to the price at
which it was bought.
·
No
trader is allowed to buy the same image more than once.
A new image has just appeared on the
market. Trader 0 bought it from an unknown artist for the price of 0, and he is
now ready to trade it among his fellow art lovers. You are given the prices, at
which traders can buy the image at each other. Assuming all transactions obey
the rules mentioned above, determine the longest possible sequence of
transactions involving the new image. After all the transactions are done,
print the number of people who have owned the image at some point in time,
including both the final owner and trader 0.
Input. Consists of multiple test cases, each test
has the following description. The first line contains the number of image
traders n (2 ≤ n ≤ 15). Each of the next n lines contains n digits. They describe the price matrix, where the j-th character of the i-th line is a digit representing the
price at which trader j will buy the
image from trader i. It is known that
0 is the lowest price, and 9 is the highest.
Output. For each tests case determine the longest
possible sequence of transactions involving the new image and print the number
of people who have owned the image at some point in time, including both the
final owner and trader 0. The answers for each test case print in a separate
line.
Sample
input
2
01
10
3
022
101
110
5
01231
00231
00031
00002
00000
Sample
output
2
2
4
SOLUTION
dynamic programming - masks
Algorithm
analysis
Состоянием будем называть тройку (mask, last, cost), обозначающую тот факт, что на данный момент владельцем
картины является продавец с номером last, он заплатил за новую картину цену cost, а картиной
не владели только те продавцы, на местах которых в mask стоят 0. Например, состояние (00101112, 2, 5)
говорит о том, что второй продавец приобрел картину стоимостью 5, причем
картиной еще не владели 3, 5 и 6 продавцы (крайняя справа единица в маске
соответствует нулевому продавцу).
Начальное состояние имеет вид
(1, 0, 0) – нулевой продавец приобрел картину за цену 0 и может продать ее
любому из продавцов.
Функция
solve(mask, last, cost) возвращает
наибольшее количество продавцов, которые могут владеть новой картиной, если на
данный момент продавец с номером last
приобрел картину стоимостью cost, а
продавать картину можно только тем продавцам, которым в маске mask соответствуют нули. Если текущий
продавец никому продать картину не может, то наибольшая длина пути картины
равна количеству единиц в двоичном коде числа mask.
Совершаем
перебор всех возможных продаж с запоминанием всех состояний в массиве m.
Example
Рассмотрим второй пример. Нулевой продавец
может продать имеющуюся изначально у него картину или первому или второму
продавцу за сумму 2. Таким образом при продаже первому продавцу мы переходим из
начального состояния (1, 0, 0) в (112,
1, 2). Если нулевой продавец продаст картину второму продавцу, то переходим в
состояние (1012, 2, 2). В обоих
случаях дальнейшая продажа картин не возможна: ни первый ни второй продавец не
в состоянии перекупить картину ценой 2.
Algorithm
realization
Значение функции solve(mask, last, cost) будем хранить в ячейке m[mask][last][cost] трехмерного массива m. Поскольку число торговцев не
больше 15, то mask ≤ 215
– 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);
}