我已经被这个问题困扰了一段时间，所以任何建议都将不胜感激
我试图将一个完全连接的有向加权图分成两个具有最小累积权重的子图。但是对于 10^5 个节点，这在计算上似乎是不可行的。
问题出处： 我们得到一个字符串，我们的任务是找到用两个手指在键盘上键入该字符串的最短路径。在开始时，我们的手指按照我们的选择定位。 然后，对于每个字母，您都可以用两根手指中的任意一根输入。 两个键之间的距离是它们之间的曼哈顿距离。 键盘看起来像这样： qwertyuiop 阿斯达夫格赫尔 zxcvbnm 按键位于方形网格中。 所以q到a的最短距离是1，q到s的最短距离是2，p到n的最短距离是6。 字符串仅由字母组成。 解决方案应该适用于长度为 < 10^5
的字符串再次感谢您的任何想法
我尝试了一种贪心的方法，但它没有用，因为第二根手指的最佳起始位置取决于字符串中的字母。
然后我将问题重新表述为将一个完全连接的有向加权图分成两个具有最小累积权重的子图。但这种方法在计算上似乎不可行。
将键盘分为左右。
qwert yuiop
asdfg hjkl
zxc vbnm
将手指 1 分配给出现在左侧的字符串中的第一个字母
将手指 2 分配给出现在右侧的字符串中的第一个字母
构造使手指保持在最初分配的一侧的路径
“你好世界”
finger 1 : e w r d
finger 2 : h l l o o l