我在usaco上的算法上发现了一个问题，我无法链接到实际问题，因为它需要身份验证，因此将其粘贴。
您刚刚赢得了一场比赛，该奖项是在加拿大免费度假。您必须通过空中行驶，城市是从东到西的。此外，根据规则，您必须从更西方的城市开始，仅向东行驶，直到到达最远的城市向东，然后仅向西飞行直到到达起点。此外，您可能不会访问一次以上的城市（当然，除了开始的城市）。
鉴于城市的顺序，可以进行航班（您只能在某些城市之间飞行，而仅仅因为您可以从城市A飞往城市B并不意味着您可以飞行另一个方向），请计算您可以访问的最大城市数量。
这是有关动态编程的教程文本的一部分。教程中还提出了解决方案的建议。
想象一下有两个旅行者在西部最大的城市开始。旅行者轮流向东行驶，下一个搬家的旅行者始终是西部最大的旅行者，但是旅行者可能永远不会在同一城市，除非它是第一个城市或最后一个城市。但是，只有一名旅行者才能进行"反向航班"，他可以从城市到城市B旅行，并且只有从城市到城市A。
的航班可以看到两个旅行者的路径可以通过将正常旅行者的路径带到东部最多的城市，然后将另一个旅行者的路线倒回去，这并不是很难创建往返的道路。到西方的城市。另外，当旅行者X被移动时，您知道旅行者Y尚未访问旅行者X以东的任何城市，除了City Traveler Y最新，否则旅行者Y必须移动一次，而X X以西Y。
据我了解解决方案，我认为可以通过在向前的方向上保留一个尺寸的桌子来完成解决方案，而可以将外向的城市朝向逆向方向来完成。例如。如果我有5个城市，则a，b ... e以所需的方向为导向，并且城市之间的有向图是一个开始城市，而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 IE来填充。访问的最大城市数量，然后在下一个条目扫描所有以前的城市的所有城市，然后选择最大值，对反向旅行者进行相同的操作。
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。这不是作业问题
您的方法与两个表格的两个表格为每个旅行者的状态建模，因为已经访问过的城市数量，并结合了该旅行者当前留住的位置。当您发现自己时，这不会阻止两次去城市。
相反，我使用三个要素来模拟状态：一个旅行者目前所在的城市，另一个旅行者所在的城市以及他们总共访问的城市数量，即个人计数的总和。因此，您将有一个2D表，而不是两个1D表。牢房（ f ， r ）将包含远期旅行者在城市 f 时，访问量的总数最多，而反向旅行者为在城市 r 。
您可能会按照其最小元素在这些状态上迭代。这意味着您接下来会扩展一个尚未扩展的状态，而这两个数字中的较小的状态在所有未表达的状态中都很少。如果处于这种状态，则 f ＆lt; r ，然后使用 f'> r ，如果有从 f 到 f'的航班。另一方面，如果 r ＆lt; f 您更新（ f ， r'）， r'>> f 和从 r'到 r 。
的航班pseudocode：
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