algorithm - 动态规划，最小化成本？

Question

我遇到了这个问题:

您必须乘坐汽车穿过一个城市的 N 个街区，从街区 0 开始，到街区 N - 1 结束。每个街区 i 都有一个加油站，在街区提供天然气，从街区到街区以西的 X[i] 英里和 Y [i] 街区以东英里。加油站仅在支付初始金额 C[i] 后才为您服务。假设所有街区都位于一条笔直的道路上。给出一种算法，该算法选择要支付的加油站，使得支付给加油站的现金最少，并且至少有一个加油站在路上的每个位置提供服务。

我尝试过的事情:

• 蛮力 - 尝试所有可能的组合并找到最佳组合 - 效果完美但耗时太长。
• 贪心 - 我试着在 1) 成本 2) 覆盖的距离 3) 每距离成本上贪心。

经过巨大的努力，我得出结论，这可能是一个动态规划问题。

尝试动态规划 - 我试图想出一个完全没有结果的循环，我发现最困难的部分是该站在两侧都提供。为了克服这个问题，我决定将站点“移动”到最西边的位置，并将东边的传送范围增加相同的数量——无法继续。

我发现了一个我认为类似的问题，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

Answer 1

据我了解，我们想要覆盖所有街区的最低成本加油站集。这可以表述为下图中的最短路径问题。为每个加油站创建一个人工源、一个人工汇和一个顶点。对于 i < j , i第一个加油站有一个弧形到j th 加油站当且仅当他们的覆盖范围没有差距。人工来源对覆盖街区的每个加油站都有弧形 0 .人造水槽有来自覆盖街区的每个加油站的弧形 n-1 .每个弧的成本是其头部加油站的成本(0 用于人工水槽)。找到从源到汇的最短路径；我们沿途访问的顶点是我们应该购买保险的加油站。

运行时间为O(n^2)对于无环有向图，通常使用线性时间最短路径算法。 O(n) 可能有所改进;查看discussion on CS . (Yuval 指定了 O(n log n) 时间，但这只是因为他在不同的计算模型中工作，其中排序是 Omega(n log n)。)