問題10635 uvaの最長共通サブシーケンスから O(nlog n) 最長増加サブシーケンスへの削減を行う方法。問題を解決するために適用されるロジックに関して、助けが必要です。
質問する
803 次
1 に答える
2
2 人のキャラクターのうちの 1 人のルートの各ステップ (プリンセスとしましょう) について、王子のシーケンスでこのステップの番号を割り当てます。
最初の観察 - 王子のシーケンスに存在しないすべてのステップはすぐに削除されます - それらは共通の一連の動きの一部になることはできません。
これで、王子の一連の動きのインデックスを表す一連の数字ができました。そのシーケンスの最大長の増加するサブシーケンス (王子と同じ順序でセルを訪問する必要があるため、増加する) を選択する必要があります。ベルを鳴らしますか？
お役に立てれば。
于 2012-05-23T16:14:08.560 に答える