4

我试图解决这个问题 - http://www.spoj.pl/problems/LISA/

我最初想到了 Greedy，但后来意识到它行不通。这似乎是一个DP问题。我无法形成递归关系。我无法形成递归关系。不只是这个问题，每当我遇到一个稍微困难的DP问题时，我都会卡住。我知道这一定很常见，实践会有所帮助。但我只是从一个问题转移到另一个问题而没有真正找到解决方案。

对于上述问题和一般情况下，DP 遇到的任何建议都会很棒。

非常感谢。

4

3 回答 3

5

请注意，允许的操作只有+和*- 关于两个操作数严格递增的二元操作（它们是正数）。

令dp[l][r]为子串 [l,r] 的最大结果

以下是有关此问题的提示，也适用于每个 dp。

1) 什么是基本情况？（提示：非常简单的东西，不会通过添加/删除括号来改变它的值）

2) 你如何从大问题转移到小问题？（提示：您可以尝试找到上次操作的位置）

于 2012-06-23T07:54:11.777 回答
0

解决这个问题只需要一个简单的矩阵链乘法实现。

于 2013-10-17T22:16:48.497 回答
0
  1. 将有 n/2+1 个数字
    1. n/2 符号
    2. 为每个符号分配剩下的数字。
    3. 创建一个方阵用相应的数字初始化对角线，现在 i,j=max((i,k)(sign right of kth number)(k+1,j)) i<=k
    4. (0,m-1) 将是答案
    5. 请注意，它将流向（0，m-1），因此是 DAG（有向无环图）。
    6. 拇指规则：如果问题的任何图形表示可以优化为 DAG，则可以通过 DP 解决

有关解决方案，请参阅： https ://shashankmishracoder.wordpress.com/2019/03/29/spoj-lisa-matrix-chain-multiplication-variation/

于 2019-03-29T16:15:55.777 回答