Q&A
B i+1 = B i + 1 が漸化式なのでは？
画像の問題をDPを使って解くように求められたのですが、どの部分に漸化式が成立するのか分かりません。テーブル配列とDPの更新式をどう作れば良いか教えてください。(1<=N<=10^5,1<=Ai<=10^5)
例A=[8, 6 ,1, 2, 7, 9]の時、求めるインデックスは[1,6]
回答2件
0
ベストアンサー
L[i] := 最後がiであるBの条件を満たす部分列の最長の長さ
とすると
L[A[i]] = L[A[i] - 1] + 1
です。
最長の部分列が複数ある場合の辞書順最小のインデックス列については、すべて更新し終わった後、最長の部分列の長さを l としたときにL[A[i] + l - 1] == lを満たす最初のインデックスからどん欲に条件を満たすインデックスをとっていけば作れます。
投稿2020/05/27 18:08
総合スコア2047
回答ありがとうございます。入出力例を追加しました。問題文の書き方が悪かったのですが、BというのはAの中で連続している制約がないようです。この場合どうなるでしょうか
その場合の漸化式です
0
（回答を取り下げさせてください）
投稿2020/05/27 17:34
編集2020/05/28 00:16
総合スコア2413
回答ありがとうございます。入出力例を追加しました。問題文の書き方が悪かったのですが、BというのはAの中で連続している制約がないようです。この場合どうなるでしょうか
あなたの回答
tips
プレビュー
