4

私はこの問題を解決しようとしていました - http://www.spoj.pl/problems/LISA/

最初はグリーディを考えましたが、後でそれがうまくいかないことに気付きました。DPの問題のようです。再帰関係を形成できません。再帰関係を形成できません。この問題だけでなく、ちょっと難しいDP問題に出くわすと必ず行き詰まります。これは一般的なことであり、練習が役立つことはわかっています。しかし、実際に解決策を見つけることなく、ある問題から別の問題に移動しているだけです。

上記の問題と、一般的にDPの遭遇について、どんなアドバイスも素晴らしいでしょう。

どうもありがとう。

4

3 に答える 3

5

許可される演算は、両方のオペランドに関して厳密に増加している二項演算のみ+であることに注意してください（これらは正です）。*

部分文字列[l、 r dp[l][r]]からの最大の結果とします

この問題に関するヒントを次に示します。これはすべてのdpにも当てはまります。

1）ベースケースとは何ですか？（ヒント：角かっこを追加/削除しても値が変わらない、非常に単純なもの）

2）大きな問題から小さな問題にどのように移行しますか？（ヒント：最後の操作の場所を見つけることを試みることができます）

于 2012-06-23T07:54:11.777 に答える
0

この問題を解決するには、Matrix Chain Multiplication の単純な実装が必要です。

于 2013-10-17T22:16:48.497 に答える
0
  1. n/2+1 の数字があります
    1. n/2 符号
    2. それぞれの符号を残りの番号で割り当てます。
    3. 正方行列を作成します 対角線を対応する数値で初期化します。ここで i,j=max((i,k)(k 番目の数値の右側に符号)(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 に答える