1

Codechef でこの問題の再発関係を見つけようとしています。

http://www.codechef.com/problems/BWALL

見つけたら、行列の累乗を使用して簡単に解くことができます。しかし、正しい答えを得る方法を理解するのに苦労しています。ここに解決策がありますが、誰かがそれをより良い方法で説明してくれませんか?

ここに画像の説明を入力 ここに画像の説明を入力 ここに画像の説明を入力

再発またはそのようなものを見つけるための簡単な経験則はありますか? ありがとう！

4

1 に答える 1

1

再発を見つけるための「一般的なルール」は、問題の解決策がより小さな問題の解決策にどのように関連しているかを理解することです。しかしそれ以上に、再発を見つけるための一般的な手順はないと思います。

この特定の例では、再発を見つける方法を次に示します。

サイズ N の大きな壁があるとします。ここで、壁の端を見てください。より正確には、壁の端から、「垂直方向の分離」がある最初の場所、つまり壁を L 字型にならずに 2 つの小さな壁に分割できる最初の場所を見つけます。

例：

(A) ここに壁があります:

X###X#XXX#X

XX#XX#XXXXX

最後に分割すると、次のようになります。

X###X#XXX #X

XX#XX#XXX XX

(B) もう一つの壁

X####X#XXX

XX#XX#XXX

最後に分割すると、次のようになります。

X####X# XXX

XX#XX# XXX

壁の割れ目と端の間にある小さな壁片のサイズはどれくらいですか? そうですね、1 つ、2 つ、または 3 つ持つことができますが、それ以上にすることはできません (それ以外の場合は、最小の分割を行うことができます)。

小さなピースの可能性は、実際にはあなたの質問で与えられたものです (はい、7 つの小さなブロック)。

したがって、サイズ N の壁を構築するには、次のことを行う必要があります。

  • サイズ N-1 の壁を構築し、サイズ-1 の小さなブロックの最後に追加します
  • またはサイズ N-2 の壁を構築し、4 つのサイズ 2 ブロックの 1 つを端に追加します。
  • または、サイズ N-3 の壁を構築し、サイズ 3 の 2 つのブロックのうちの 1 つを端に追加します。

したがって、サイズ N の可能な壁の数 T(N) は

  • サイズが N-1 の壁の数 (最後にサイズが 1 のブロックがある) -> T(N-1)
  • 4 つの可能なエンド ブロック (サイズ 2 の場合) を持つサイズ N-2 の壁の数に加えて -> 4 T(N-2)
  • サイズ N-3 の壁の数に加えて、2 つの可能なエンド ブロック (サイズ 3 の場合) -> 2 T(N-3)

そして、そこにあなたの再発があります。

それが役に立てば幸い！

于 2013-01-29T10:19:36.403 に答える