2

我在usaco上的算法上发现了一个问题，我无法链接到真正的问题，因为它需要身份验证，所以粘贴它。

你刚刚赢得了一场比赛，奖品是在加拿大的一次免费假期。您必须乘飞机旅行，并且城市从东到西排列。此外，根据规则，您必须从较远的城市西部开始，仅向东行驶，直到您到达最东边的城市，然后仅向西飞行，直到您到达起始位置。此外，您不能多次访问任何城市（当然，起始城市除外）。

给定城市的顺序，加上可以做的航班（你只能在某些城市之间飞行，仅仅因为你可以从A城市飞到B城市并不意味着你可以飞另一个方向），计算最大数量您可以访问的城市。

这是关于动态规划的教程文本的一部分。教程中还给出了解决方案的建议。

想象一下有两个旅行者从最西部的城市开始。旅行者轮流向东旅行，下一个要移动的旅行者总是最西端，但旅行者可能永远不会在同一个城市，除非它是第一个或最后一个城市。但是，其中一名旅客只允许进行“反向飞行”，即当且仅当有从 B 市到 A 市的航班时，他才能从 A 市前往 B 市。

不难看出，两个旅行者的路径可以组合成一个往返，先走正常旅行者的路径到最东边的城市，然后再走另一个旅行者的相反路径回到西部。 - 大多数城市。此外，当旅客 x 移动时，您知道旅客 y 尚未访问旅客 x 以东的任何城市，但旅客 y 当前所在的城市除外，否则旅客 y 必须在 x 在 y 以西时移动过一次。

据我了解的解决方案，我认为可以通过保持一个正向的去向城市的一维表和一个反向的去向城市的表来完成该解决方案。例如。如果我有 5 个城市，A，B...E 以所需方向定向，城市之间的有向图是 A 是起始城市，E 是目的地。

   A | B | C | D | E
A  0 | 1 | 0 | 0 | 0
B  0 | 0 | 1 | 1 | 0
C  1 | 0 | 0 | 0 | 1
D  0 | 0 | 0 | 0 | 1
E  0 | 0 | 1 | 0 | 0

我为即将离任的城市保留了两张表，我将通过将第一个城市初始化为 1 来填充它。访问的最大城市数量，然后为每个下一个条目扫描所有先前存在的路径到当前城市的城市，然后选择最大值，对反向旅行者做同样的事情。

table[i] = Max(j=i to 0) (table[j])

我将在目的地城市获得最大值，但这并不能保证任何城市都不会重复。如果我在数组字段中再保留一个条目以及最大数量，我将无法将其从正向切换到反向。我正在学习动态编程，所以可能我没有得到正确的想法。这是我为图表构建的表格

A | B | C | D | E
1 | 2 | 3 | 3 | 4
1 | 1 | 2 | 1 | 3

所以将从两者中获得最大收益。请提供方向/提示，以便我可以朝着正确的方向前进。

PS。这不是作业问题

4

1 回答 1

0

您使用这两个表格的方法独立地模拟了每个旅行者的状态，作为已经访问过的城市数量，以及该旅行者当前停留的位置。正如您自己发现的那样，这不会阻止您两次访问一个城市。

相反，我将使用三个元素来模拟状态：一位旅行者当前所在的城市，另一位旅行者所在的城市，以及他们总共访问过的城市数量，即他们个人计数的总和。所以你会有一个 2d 表，而不是你的两个 1d 表。当前向旅行者在城市f并且反向旅行者在城市r时，单元格 ( f , r ) 将包含已知的总访问城市数。

您可能会按照它们的最小元素的顺序遍历这些状态。这意味着您接下来将扩展一个尚未扩展的状态，并且这两个数字中较小的一个在所有未扩展的状态中最小。如果处于该状态，f < r ，那么如果有从f到f'的航班，您将使用它来使用f' > r更新状态（ f'，r）。另一方面，如果r < f你更新 ( f , r' ) 与r' > f和来自r'的航班

在伪代码中：

first = (f: 0, r: 0)  # tuple with two members, called f and r
todo = set { first }  # a set with a tuple as its only element
visited = a map from tuples to integers, unset values defaulting to 0
visited[first] = 1
while todo is not empty:
  best = ∞
  cur = null
  for t in todo:
    if min(t.f, t.r) < best:
      best = min(t.f, t.r)
      cur = t
  todo.remove(cur)
  if (cur.f < cur.r):
    for f' in cities where flights from f arrive:
      next = (f: f', r: cur.r)  # keep r but use f' as the new f
      todo.add(next)            # will do nothing if it already is in the set
      visited[next] = max(visited[next], visited[cur] + 1)
  else:
    for r' in cities where flights to r depart:
      next = (f: cur.f, r: r')
      todo.add(next)
      visited[next] = max(visited[next], visited[cur] + 1)
best = 0
for cur in keys of visited:
  if best < visited[cur]:
    if there is a flight from cur.f to cur.r: # can close the tour
      best = visited[cur]
return best
于 2012-10-26T21:10:32.117 回答