algorithm - 动态规划 : Timus Online Judge 1172 Ship Routes

Question

这个问题困扰我好久了。它必须具有动态编程解决方案，因为它已被标记为“动态编程”。请提出一个方法。

Question Link

简化的问题陈述:

There are 3 islands having N cities on each of them. There is a path from every city on an island to every city on another island, ie. there is no path connecting cities on the same island. Find the number of ways of visiting all the 3*N cities. Note that 2 trips are identical if the successions of the 3*N cities are identical or if the succession of the 3*N cities of the first trip is the same as the succession of the 3*N cities of the 2nd trip, read backwards (for instance, if every island had 1 city, numbered according to the island's number, the trips 1-2-3-1 and 1-3-2-1 would be identical).

约束:

1 ≤ N ≤ 30

示例输入/输出:

For N=2, answer = 16.

Answer 1

这只是我的想法:

首先，如果我们能解决两个子问题，我们就可以解决问题

• 假设您需要生成一个长度为 3*N 的字符串，仅由 1 、 2 或 3 组成，计算我们可以通过多少种方式来创建这个字符串，条件是1、2 或 3 没有连续出现 2 次 ，并且对于每种类型的字符，字符串中应该有 N 个。你可以用DP解决这个问题

• 其次，从所有创建的字符串中，删除第一个字符，因为字符串可以前后读取的条件相同，所以每个字符串将被计算两次，回文除外 .所以，我们需要计算这 3*N - 1 个字符串的回文数。这个可以通过DP来解决

现在，我们可以用岛 1、2 或 3 中的一个城市替换字符串中 1,2 或 3 的每个位置，并且有 (N!)^3 种方法可以为每个字符串执行此操作，我们有答案