Codechef でこの問題の再発関係を見つけようとしています。
http://www.codechef.com/problems/BWALL
見つけたら、行列の累乗を使用して簡単に解くことができます。しかし、正しい答えを得る方法を理解するのに苦労しています。ここに解決策がありますが、誰かがそれをより良い方法で説明してくれませんか?
再発またはそのようなものを見つけるための簡単な経験則はありますか? ありがとう!
Codechef でこの問題の再発関係を見つけようとしています。
http://www.codechef.com/problems/BWALL
見つけたら、行列の累乗を使用して簡単に解くことができます。しかし、正しい答えを得る方法を理解するのに苦労しています。ここに解決策がありますが、誰かがそれをより良い方法で説明してくれませんか?
再発またはそのようなものを見つけるための簡単な経験則はありますか? ありがとう!
再発を見つけるための「一般的なルール」は、問題の解決策がより小さな問題の解決策にどのように関連しているかを理解することです。しかしそれ以上に、再発を見つけるための一般的な手順はないと思います。
この特定の例では、再発を見つける方法を次に示します。
サイズ 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 の可能な壁の数 T(N) は
そして、そこにあなたの再発があります。
それが役に立てば幸い!