动态规划，最小化成本？
Dynamic programming, minimizing cost?
我遇到了这个问题：
您必须乘坐汽车从 0 街区开始，并在 N - 1 街区结束，穿越城市中的 N 个街区。每个街区 i 都有一个加油站，从街区到街区以西 X[i] 英里和街区以东 Y[i] 英里的街区提供天然气。加油站仅在支付初始金额 C[i] 后才为您服务。假设所有街区都位于一条笔直的道路上。给出一种选择加油站支付的算法，使得支付给加油站的现金最少，并且至少有一个加油站在路上的每个位置交付。
我尝试过的事情：
- 蛮力 - 尝试了所有可能的组合并找到了最佳组合 - 效果完美但耗时太长。
- 贪心 - 我试图在 1) 成本 2) 覆盖的距离 3) 每距离成本上贪心。
经过艰苦的努力，我得出结论，这可能是一个动态规划问题。
尝试动态规划 - 我试图想出一个完全没有结果的重复，我发现最困难的部分是站的两侧都提供。为了克服这个问题，我决定 "move" 将站点放在最西边的位置，并将东边的传送范围增加相同的数量 - 无法继续。
我发现了一个我认为类似的问题，dynamic programming proboem for minimum cost
这些问题真的很相似吗？
有人可以告诉我这是否实际上 是一个动态规划问题并且没有其他更有效的方法吗？
如果是动态规划，你能给我一些提示吗？
示例：
Suppose N is 4
block 0 : X = 1, Y = 1, C = 2
block 1 : X = 0, Y = 2, C = 1
block 2 : X = 2, Y = 2, C = 5
block 3 : X = 1, Y = 5, C = 7
Then the result will be,
Pay block 0, 1 gas stations.
Min cost : 3
据我了解，我们想要覆盖所有街区的最低成本加油站。这可以表述为下图中的最短路径问题。为每个加油站创建一个人工源、一个人工汇和一个顶点。对于 i < j，第 i 个加油站与第 j 个加油站有一条弧线，当且仅当它们的覆盖范围没有间隙时。人工来源与覆盖区块 0 的每个加油站都有弧线。人造水槽的弧线来自覆盖区块 n-1 的每个加油站。每条弧线的成本是其头部加油站的成本（0 为人工水槽）。找到从源到汇的最短路径；我们沿途访问的顶点是我们应该购买保险的加油站。
运行时间是O(n^2)与无环有向图通常的线性时间最短路径算法。 O(n) 可能有改进；见discussion on CS。 （Yuval 指定了 O(n log n) 时间，但这只是因为他在不同的计算模型中工作，其中排序是 Omega(n log n)。）
我遇到了这个问题：
您必须乘坐汽车从 0 街区开始，并在 N - 1 街区结束，穿越城市中的 N 个街区。每个街区 i 都有一个加油站，从街区到街区以西 X[i] 英里和街区以东 Y[i] 英里的街区提供天然气。加油站仅在支付初始金额 C[i] 后才为您服务。假设所有街区都位于一条笔直的道路上。给出一种选择加油站支付的算法，使得支付给加油站的现金最少，并且至少有一个加油站在路上的每个位置交付。
我尝试过的事情：
- 蛮力 - 尝试了所有可能的组合并找到了最佳组合 - 效果完美但耗时太长。
- 贪心 - 我试图在 1) 成本 2) 覆盖的距离 3) 每距离成本上贪心。
经过艰苦的努力，我得出结论，这可能是一个动态规划问题。
尝试动态规划 - 我试图想出一个完全没有结果的重复，我发现最困难的部分是站的两侧都提供。为了克服这个问题，我决定 "move" 将站点放在最西边的位置，并将东边的传送范围增加相同的数量 - 无法继续。
我发现了一个我认为类似的问题，dynamic programming proboem for minimum cost 这些问题真的很相似吗？
有人可以告诉我这是否实际上 是一个动态规划问题并且没有其他更有效的方法吗？ 如果是动态规划，你能给我一些提示吗？
示例：
Suppose N is 4
block 0 : X = 1, Y = 1, C = 2
block 1 : X = 0, Y = 2, C = 1
block 2 : X = 2, Y = 2, C = 5
block 3 : X = 1, Y = 5, C = 7
Then the result will be,
Pay block 0, 1 gas stations.
Min cost : 3
据我了解，我们想要覆盖所有街区的最低成本加油站。这可以表述为下图中的最短路径问题。为每个加油站创建一个人工源、一个人工汇和一个顶点。对于 i < j，第 i 个加油站与第 j 个加油站有一条弧线，当且仅当它们的覆盖范围没有间隙时。人工来源与覆盖区块 0 的每个加油站都有弧线。人造水槽的弧线来自覆盖区块 n-1 的每个加油站。每条弧线的成本是其头部加油站的成本（0 为人工水槽）。找到从源到汇的最短路径；我们沿途访问的顶点是我们应该购买保险的加油站。
运行时间是O(n^2)与无环有向图通常的线性时间最短路径算法。 O(n) 可能有改进；见discussion on CS。 （Yuval 指定了 O(n log n) 时间，但这只是因为他在不同的计算模型中工作，其中排序是 Omega(n log n)。）