动态规划: Timus在线评判1172条航线
动态规划: Timus在线评判1172条航线
提问于 2014-04-02 04:41:30
很长时间以来，我一直被困在这个问题上。它必须有一个动态规划解决方案，因为它被标记为“动态规划”。请建议一个办法。
问题链接
简略问题陈述：
有3个岛屿，每个岛上都有N个城市。从一个岛上的每一个城市到另一个岛上的每一个城市都有一条小路。在同一座岛上没有连接城市的道路。找出参观所有3*N城市的方法。注意，如果3*N城市的接续是相同的，或者如果第一次旅行的3*N城市的继承与第二次旅行的3*N城市的继承相同，则2次旅行是相同的(例如，如果每个岛屿都有1座城市，根据岛上的编号编号，则1-2-3-1和1-3-2-1将是相同的)。
制约因素：
1≤N≤30
样本输入/输出：
对于N=2，回答= 16。
回答 1
Stack Overflow用户
回答已采纳
发布于 2014-04-02 06:29:50
这只是我的想法：
首先，如果我们能解决两个子问题，我们就可以解决这个问题。
- 假设您只需要从1、2或3 生成一个长度为3*N的字符串，计算创建该字符串的方式有多少种，条件是没有连续出现1、2或3的，对于每种类型的字符，字符串中应该有N个字符串。您可以使用DP解决这个问题。
- 其次，从创建的所有字符串中移除第一个字符，因为字符串可以同样地向后和向前读取，因此每个字符串将被计数两次，除了回文。因此，我们需要计算这3*N -1字符串的回文数。这可以通过DP来解决。
现在，我们可以将字符串中的1,2或3的每个位置替换为岛1、2或3中的一个城市，对于每个字符串有(N!)^3的方法，我们得到了答案。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/22801735
复制相关文章
相似问题
腾讯云开发者
