2

書かなければならないプログラムがありますが、その方法がわかりません。それを解決する方法の参照が必要です。問題は次のとおりです。N 個の整数
のリストがあります。例: [4;2;3;2;1;5;1;3;2]。隣接する重複番号がK個以上 ある場合、それらはリストから削除されます。任意の 2 つの数字の間、またはリストの先頭/末尾に任意の数字を追加して、その数字がリストから削除されるようにすることができます。

タスクは、できるだけ少ない数字を使用してリストをクリアすることです。

1 <= N <= 100 - Nはリストの長さです。
2 <= K <= 5 - Kは、シーケンスから削除される重複した隣接番号の最小量です。

Kは指定された範囲で提供されます。

例: List = [4;2;3;2;1;5;1;3;2] - 答えは3です。K = 2

私の考えは、数値を効率的に削除するために、ある種のシーケンス ツリーを用意することです。この例のツリーは次のようになります。

4 2       2
   3     3
    2 1 1
       5

したがって、リストの 4 番目と 5 番目の要素 (0 から開始) の間に5を追加する必要があり、4 番目から 7 番目の要素が消え、シーケンスは次のようになります。

4 2   2
   3 3
    2

ここで、新しいシーケンスの 2 番目と 3 番目の要素の間に2を追加すると、1 番目から 5 番目の要素が削除されます。

次に、新しい数列に 4 を追加すると、数列に追加された合計数は3でした。この問題のアルゴリズムは何ですか? ありがとう。

4

1 に答える 1

0

問題をリバース エンジニアリングしてみましょう。あなたの例を考えると、外出先で減らすことができる最終的な文字列は次のようになります

4           4
 2         2
  3       3
   2     2
    1   1
     5 5

気がつけば、それは等長の回文です。同様のことが、可能な他のすべての入力にも当てはまります。

ここで、問題は、入力内の最長の回文サブシーケンスを見つけて、回文サブシーケンスにない入力内のすべての文字に対応する入力文字列に文字を追加することに減らすことができます。最長の回文サブシーケンスを見つけることは、標準的な DP 問題であり、チュートリアルはここにあります。

たとえば、あなたの場合、最長のサブシーケンスは で[2,3,1,1,3,2]あり、入力に含まれていない文字は である[4,2,5]ため、これらを入力に追加するか、数字に興味がある場合3は答えになります。

于 2012-10-26T12:28:51.597 に答える