代码之家 › 专栏 › 技术社区 › anirudh

给定具有正整数值的大小MxN的2D矩阵,找到具有最大和的闭环。

optimization matrix algorithm

anirudh · 技术社区 · 7 年前

循环可以是任意形状,但只能上/下/左/右。循环的和被定义为沿其周长的所有唯一元素的和。循环不允许交叉本身,因为这是次优的(因为我们不允许对同一个元素计数两次)。

有人知道在多项式时间内可以用来解决这个问题的方法吗?有人问我这个问题,但我不知道怎么做与DP或其他。

编辑-循环也应该是凸的。

1 回复 | 直到 7 年前

btilly 7 年前

这是DP解决方案的概要。

对于每一对点,找到最大凸弧,如果它弯曲,弓远离左下角。

对于每一对点,找到最大凸弧,如果它弯曲,弓远离右上角。

找到这两个圆弧之和最大的点对。那对弧线就是你的答案。

推荐文章

AstralHex · 矩阵乘法代码工作不正常

5 月前

Baba Dan Constantin · SSE4.1在矩阵4x4乘法上比SSE3慢?

5 月前

Max · 用两列中的特定值对识别R中的数据帧行

7 月前

RobertF · 如何将函数应用于矩阵的每个元素?

7 月前

Leprechault · 使用数据帧创建对象类“matrix”“array”

7 月前

Landers · 将矩阵转换为包含所有值的列表

11 月前

P_B · 如何从矩阵中减去均值向量

11 月前

Rotacional · 获取矩阵中的方向元素

1 年前

ImRobb · 为什么int**m不等于int m[][]?[关闭]

1 年前

Suyash Nachankar · 为什么矩阵的所有行都与最后一行相同?

1 年前