gpt4 book ai didi

algorithm - 动态编程 : Tennis Balls, 储物柜和 key

转载 作者:塔克拉玛干 更新时间:2023-11-03 05:01:14 24 4
gpt4 key购买 nike

<分区>

我在寻找问题的最佳动态规划解决方案时遇到困难,非常感谢任何帮助。最优解为O(T^2+M);我只能找到 O(NM^2) 的解决方案。问题是:

有 N 个标记为 1,2...N 的储物柜。每个储物柜都上锁,但可以使用其唯一的 key 打开。每个储物柜的 key 副本都在其相邻的储物柜中;即储物柜 i 的 key 副本放在储物柜 i+1 和 i-1 中(储物柜 1 的 key 仅在储物柜 2 中,储物柜 N 的 key 仅在储物柜 N-1 中)

T 个网球在 T 个不同的储物柜中(你知道它们在哪个储物柜中)。您获得了 M 个储物柜的 key ,您的目标是通过打开最少数量的储物柜来收集所有网球。

我给出的唯一提示是:提示:你能否有效地判断第 i 个和第 j 个储物柜之间是否至少存在一个网球?

24 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com