mar*_*rti 7 algorithm dynamic-programming
你有N个守卫在一条线上,每个都需要硬币.只有当他的要求低于你到达他之前已经完全支付的费用时,你才可以跳过支付警卫.找到你花在跨越所有警卫的最少数量的硬币.
我认为这是一个DP问题,但无法提出一个公式.另一种方法是对答案进行二元搜索,但如何验证是否有多个硬币是可能的答案？
这确实是一个动态编程问题.
考虑一下这个函数f(i, j),它是true(一)是否有第一个i为你付出代价的警卫j.您可以f(i, j)在大小的表格中安排功能n x S,其中S是所有警卫需求的总和.
让我们表示d_i作为守卫的需求i.f(i+1)如果您f(i)只需扫描f(i)并指定f(i+1, j + d_i)为一个,如果f(i + 1, j)为真j < d_i,f(i + 1, j)则可以轻松计算列j >= d_i.
这在O(nS)时间和O(S)空间上运行(你每次只需要保留两列),这只是伪多项式(如果需求在某种程度上是有界限的,并且不随之增长,则为二次类n).
降低DP问题复杂性的常见技巧是获得B最优解的值的上限.通过这种方式,您可以修剪不必要的行,获得时间复杂度O(nB)(好吧,甚至S是上限,但是非常天真).
事实证明,在我们的案例中,警卫的最大需求B = 2M在哪里M.事实上,考虑一下这个功能best_assignment(i),它可以让你获得通过第一个i守卫的最少数量的硬币.让我们j成为需求的守护者M.如果best_assignment(j - 1) > M,那么显然整个序列的最佳任务是为第一个j-1守卫的最佳任务支付警卫并跳过其他人,否则上限由best_assignment(j - 1) + M < 2M.给出.但best_assignment(j - 1)在第一种情况下可以有多少？它不能超过2M.这可以通过矛盾来证明.让我们假设一下best_assignment(j - 1) > 2M.在这项任务中,警卫j-1是谁？不,因为2M - d_{j-1} > d_{j-1},因此不需要支付.同样的道理也适用于j-2,j-3...... 1,因此,没有后卫支付,这是荒谬的,除非M = 0(要检查的一个很天真的情况下).
由于证明了上限2M,上面用n列和2M行说明的DP 解决了问题,具有时间复杂性O(nM)和空间复杂性O(M).