（0,0）で始まり、正のx軸とy軸で無限大に進む2次元配列があるとします。数k>0が与えられた場合、（0,0）から到達可能なセルの数を見つけます。これにより、すべての瞬間->xの桁の合計+yの桁の合計<=kとなります。移動は、上、下、左、または右に行うことができます。与えられたx、y>=0。
Dfsは答えを出しますが、kの値が大きい場合は十分ではありません。誰かがこれのためのより良いアルゴリズムで私を助けることができますか？
質問する
152 次
1 に答える
0
k> = x + yで到達可能なセル（x、y）の数を計算するように求められたと思います。たとえば、x = 1の場合、yは0からk-1までの任意の数を取ることができ、合計は<=kになります。可能性の総数は、次のように計算できます。
sum(sum(1,y=0..k-x),x=0..k) = 1/2*k²+3/2*k+1
それは大きなkのトリックを行うことができるはずです。
私はあなたの質問の「数字」に少し混乱しています。数字は、3 x 9が999になるようにインデックスを構成します。セルの数字の合計（999,888）は51になります。数字の合計を10 ^ 9にすると、10^8桁になる可能性があります。インデックス。結果として、テーブルの通常のサイズをはるかに超える10 ^（10 ^ 8）エントリ程度になります。したがって、私は私の最初の解釈を想定しています。それが正しくない場合は、もう少し説明していただけますか？
編集：
さて、私の答えはそれを解決するつもりはありません。いい式や答えが見当たらないのではないかと思います。着色/マーキングの問題としてアプローチし、すべての有効なセルにマークを付けてから、他の手法を使用して、すべてのパーツが接続されていることを確認します/それらをカウントします。
私は何かを考え出そうとしましたが、それはあまりにも厄介です。基本的には、インデックスとkに基づいて、一度に大きなパーツにマークを付けようとします。k = 20の場合、セル範囲（0,0..299）を一度にマークして（インデックスが低いほどインデックスの合計が低くなるため）、残りの範囲のチェックを続行できます。299から始めて、最後の2桁を最大値に固定し、最初の桁の最大値を探します。次に、残りの数百（300-999）の間そのプロセスを続行し、最後の桁だけを修正して300..389と390..398になります。しかし、あなたはそれが混乱していることをすでに見ることができます...（それにもかかわらず、私はあなたにそれを与えたかったのですが、あなたはいくつかのより良いアイデアを得るかもしれません）
すぐにわかるもう1つのことは、問題がインデックスで対称であるため、有効なセル（x、y）があれば、別の有効なセル（y、x）があることを示します。マーキングスキーム/dfs/ bfsでは、これを利用できます。
于 2012-12-16T22:28:01.347 に答える