4

問題は次のとおりです。

  1. 「いい」について

    1) 「ab」いいですね

    2) A はいいね => "a"+A+"b" はいいね

    3) A と B がいい => A+B がいい

  2. 「～」について

    1) 「アブ」～「アブ」

    2) A~B => "a"+A+"b"~"a"+B+"b"

    3) A~B および C~D => A+C~B+D および A+C~D+B

現在、セット S を形成する 'a' と 'b' の最大 1000 個の文字列があり、すべての要素がナイスでなければならず、ペア (A,B) のいずれも A~B を保持しない S の最大のサブセットを見つけます。カーディナリティを出力します。

前に見た問題とは異なる sth があります: A+B+C+D~A+C+B+D~B+D+A+C but A+B+C+D~B+D+A+C保持しません。

私にとって2つの困難：

  1. S1～S2かどうかの確認方法
  2. すべてのペアの "~" がわかっている場合、カーディナリティを見つけるにはどうすればよいですか

詳細: https://www.spoj.pl/problems/ABWORDS/

4

1 に答える 1

1

ナイスワードを作成するためのルールは、すべてのナイスワードが「a」で始まり「b」で終わることを意味します。したがって、素敵な単語を素敵なサブ単語に分解する独自の（順序付けまで-ルール3）があります。すべての「ab」を見つけてから、ルール2を使用してそれらを展開し、ルール3を使用してシーケンスします。ツリーを介してこの分解を表現できます（ルール3を繰り返し適用するためのn個のブランチ）。

ツリーのコンテキストでは、「〜」関係は単に同型ツリーを表現していると思います（分岐の順序は重要ではありません）。

編集：指摘したように、分岐の順序は重要です。

元のリンクに記載されているように問題を解決しようとします（「nice」の2つの定義は一致しません）。

まず、DPを使用した2つの単語XとYの類似性。

に類似していて、両方のサブワードが優れているf(a, b, n)ことを示す関数であると定義します。X[a..a+2n-1]Y[b..b+2n-1]

f(a, b, 0) = 1.

n> 0の場合、

f(a, b, n) = f1(a, b, n) or f2(a, b, n) or f3(a, b, n)
f1(a, b, n) = x[a] == y[b] == 'a' and x[a+2n-1] == y[b+2n-1] == 'b' and f(a+1, b+1, n-1)
f2(a, b, n) = any(1 <= k < n) f(a, b, k) and f(a+2k, b+2k, n-k)
f3(a, b, n) = any(1 <= k < n) f(a, b+2(n-k), k) and f(a+2k, b, n-k)

これはO（n ^ 4）（うーん）だと思います。

2番目の部分では、類似関係を表すエッジを持つグラフとして単語を表す場合、基本的に最大の独立集合を見つけようとしていると思います。もしそうなら、頑張ってください！一般的なケースではNP困難（つまり、すべての組み合わせを試すよりも良い解決策は知られていない）であり、これを容易にするプロパティはありません:(

類似性の定義が自動的に良さをチェックするように編集されました。とても簡単です。

私の愚かさのためにもう一度編集しました。

于 2010-12-11T02:17:36.753 に答える