如何解决问题“4967 - Tri graphs” ICPC Live Archive

Question

首先，我很抱歉我的英语不是很好！！！这是解决该问题的 link：https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2968

简要说明：求从图上中间节点到图底部中间节点的最小成本。

一条路径的成本将是它经过的所有节点的总和。

所以，我想我应该使用LCBFS算法来解决这个问题，但是我的算法不够好，所以我的代码被超时了。这是我的代码：http://codepad.org/lJIYOPon。任何人都可以帮助我优化我的代码，非常感谢。

Answer 1

这是我解决它的方法（并得到 Accepted）：

我使用了自下而上的动态规划方法，这让我想出了一个 O(n) 时间解决方案，O(1) 用于记忆。

让我们使用动态规划 table 并计算节点在每个 row 和 col（即 dp[row][col]）上的最低成本是多少。我们将从最后一行开始，然后进行到第一行（自下而上）。

让我们将 "graph" 存储在二维数组中，称为 graph，大小为 [n][3]。

首先，如果我们处理一行（最后一行），很容易看出成本是多少。

dp[0] = graph[n - 1][0] + graph[n - 1][1]，因为如果我们在列0，然后跳到相邻列（到达目标），答案将是节点的总和第一列和第二列。
dp[1] = graph[n - 1][1]，同理
dp[2] = infinity，因为如果我们在最后一行的最后一列，我们将无法到达目标。

知道了这一点，现在假设我们的图表中有两行，我们想计算第一行的答案。请注意，第二行的答案是已知的。

如果我们在第一行（索引为 0），那么我们可以计算另一个 dp，我们称之为 next。为了计算next[1]，我们应该先计算next[2]，因为从第一列我们可以得到第二列，我们必须知道next[2].

的答案

next[2] = graph[0][2] + min(dp[1], dp[2])，因为从第一行，站在第2列，我们可以向下到下一行1和[=29]列=].我们已经知道下一行的最小值，存储在之前计算的 dp 数组中。
next[1] = graph[0][1] + min(next[2], min(dp[0], dp[1], dp[2]))。想想为什么要这样计算
next[0] = graph[0][0] + min(next[1], min(dp[0], dp[1])

我们可以以相同的方式进行并计算一般情况下 N >= 2 的最小值。

请注意，我们只能存储最后三个计算值，因为从第 i 行我们可以转到第 i + 1 行，因此我们不必存储整个 [n][3] table，但只有最后一行。这一观察将内存复杂度降低到 O(1)!

这是我在 Java 中的代码（我省略了读取输入的部分）：

private long dp(int[][] graph) {
  int n = graph.length;
  long[] dp = new long[3];
  dp[0] = graph[n - 1][0] + graph[n - 1][1];
  dp[1] = graph[n - 1][1];
  dp[2] = Integer.MAX_VALUE;

  for (int row = n - 2; row >= 0; row--) {
    long[] next = new long[3];

    next[2] = graph[row][2] + min(dp[1], dp[2]);
    next[1] = graph[row][1] + min(next[2], min(min(dp[0], dp[1]), dp[2]));
    next[0] = graph[row][0] + min(next[1], min(dp[0], dp[1]));
    dp = next;
  }
  return dp[1];
}

如何解决问题“4967 - Tri graphs” ICPC Live Archive

How to solve problem "4967 - Tri graphs" ICPC Live Archive

algorithm

breadth-first-search