динамическое программирование (Ship rootes)

[gdrt]

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

Римский турист отправился в плавание по Средиземному морю. Он прибыл в один из городов 3 островов, которые он собирается посетить. Каждый остров имеет в точности N городов и все они являются портами. турист планирует начать путешествие с того города,в котором он находится и посетить другие 3*N - 1 городов в точности один раз и затем вернуться в начальный город, чтобы вернуться обратно домой после этого.

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

Турист хочет знать, сколькими способами он может спланировать свое путешествие по 3 островам

Ввод

Содержит одно число N (1<=N<=30), то есть количество городов на каждом из трех островов

Вывод

Вывести одно число: количество способов, которыми турист может спланировать свое путешествие. Заметьте, что два путешествия являются идентичными если последовательности из 3*N городов идентичны ИЛИ если последовательность из 3*N городов первого путешествия идентична последовательности из 3*N городов второго путешествия, считанной наоборот ( например, если каждый остров имеет один город, пронумерованный в соответствии с номером острова, путешествия 1-2-3-1 и 1-3-2-1 будут идентичными

Пример ввода
2
Пример вывода
16

/* А это те 16 разных маршрутов:
1 3 5 2 4 6
1 3 5 2 6 4
1 3 6 2 4 5
1 3 6 2 5 4
1 4 5 2 3 6
1 4 5 3 2 6
1 4 6 2 3 5
1 4 6 3 2 5
1 5 2 4 6 3
1 5 3 2 4 6
1 5 3 6 2 4
1 5 4 6 2 3
1 6 2 4 5 3
1 6 3 2 4 5
1 6 3 5 2 4
1 6 4 5 2 3
*/


Лимит времени
1 секунда

Лимит памяти
16 МБ

[gdrt]

Спасибо за перевод asidorchenko

[Abstraction]

Пусть мы на острове A, число непосещённых городов на островах A, B, C - a, b, c соответственно. Пусть число путей, считая "зеркальные" пути разными - S(a, b, c). Тогда:
S(a, b, c) = 0 при b+c<a;
S(a, b, c) = (a!)^2 при b+c=a;
S(a, a+1, 0) = (a+1)*(a!)^2;
S(a, b, 0) = 0 при b!=a, b!=a+1;
S(a, b, c) = b*S(b-1, c, a) + c*S(c-1, b, a) при b+c>a.

[gdrt]

А Вы можете объяснить подробнее каждый случай? Ибо мне нужно будет обосновать решение

[Abstraction]

Да, пожалуйста. Какой непонятен?

[gdrt]

В принципе все эти 5 случаев непонятны))

[gdrt]

Сообщение от Abstraction

Да, пожалуйста. Какой непонятен?

Можете пожалуйста объяснить хотя бы подход

[Abstraction]

S(a, b, c) = 0 при b+c<a;

Если на текущем острове городов осталось больше, чем на двух других, то нет возможности совершить путешествие.

S(a, b, c) = (a!)^2 при b+c=a;

Если на текущем острове городов столько же, сколько и на двух других, то все маршруты - курсирование между этим островом и парой других, их число - (число способов упорядочить города на текущем острове)х(число способов упорядочить города на двух других островах).

S(a, a+1, 0) = (a+1)*(a!)^2;

То же для случая, когда один остров посещён, а на втором осталось на один город больше, чем на текущем.
И так далее.

Только вот кое-кто не учёл, что маршрут надо замкнуть. Это означает, что функций две: для случая, когда мы на начальном острове (S) и когда нет (R, начальный остров - B).
S(a,b,c) = (a+1)!*a! при b+c=a+1;
S(a,b,c) = 0 при b+c<=a;
S(a,b,0) = 0 при b>a+1;
R(a,b,c) = 0 при b+c<a;
R(a,b,0) = 0 при b>a;
R(a,0,c) = 0 при c>a+1;
R(a,b,c) = c*R(c-1,b,a) + b*S(b-1,a,c);
S(a,b,c) = b*R(b-1,a,c) + c*R(c-1,a,b);

Искомое (поскольку каждый путь обратим и обратный не совпадает с исходным) - S(N-1,N,N)/2.
В нашем случае: X = S(1,2,2)/2 = (2R(1,1,2)+2R(1,1,2))/2 = 4R(1,1,1)+2S(0,1,2) = 4R(0,1,1)+4S(0,1,1)+2R(0,0,2)+4R(1, 0,1) = 4R(0,1,0)+4S(0,0,1)+4R(0,0,1)+4R(0, 0,1)+2*0+4*1 = 4*0+4*1+4*1+4*1+2*0+4*1 = 16.

[gdrt]

Спасибо огромное, осталось понять только это

Сообщение от Abstraction

R(a,b,c) = c*R(c-1,b,a) + b*S(b-1,a,c);
S(a,b,c) = b*R(b-1,a,c) + c*R(c-1,a,b);

почему вы отнимаете единичку и смещаете параметры?

[Abstraction]

Число способов пропутешествовать, если я нахожусь на острове A и в конце вернуться я тоже должен на A - S(a,b,c). Первым шагом я могу либо поплыть на остров B, либо на остров C. Рассмотрим первый случай. Я могу выбрать любой из оставшихся b портов и в итоге окажусь на острове A'=B, с непосещёнными (b-1) портами на нём, и это не тот остров, на который я должен вернуться в конце. На том острове, на который я возвращаюсь в конце, B'=A, осталось a непосещённых портов; на третьем острове C'=C осталось c непосещённых портов. Таким образом, выбрав любой из b портов, я буду иметь R(b-1, a, c) вариантов завершения путешествия. Аналогично, поплыв первым шагом на остров c, я выбираю один из c портов и остаётся R(c-1, a, b) вариантов завершения путешествия. Всего: S(a,b,c)=b*R(b-1,a,c)+c*R(c-1,a,b). R(a,b,c) расписывается аналогично.