N X M左下の点が原点にある長方形のフィールドが与えられます。フィールドに正方形のベースを持つタワーを構築する必要があります。それらを根こそぎにするためのコストが関連するフィールドに木があります。したがって、タワーの建設コストを最小限に抑えるには、根こそぎにされる木の数を最小限に抑える必要があります。
入力例:
N = 4
M = 3
Lenght of side of Tower = 1
Number of Trees in the field = 4
1 3 5
3 3 4
2 2 1
2 1 2
入力の 4 行は、根こそぎにするためのコストを 3 番目の整数として持つツリーの座標です。
塔の端にある木は塔の内部にあると見なされ、根こそぎにする必要があります。
この問題の動的計画法の関係を定式化する際に問題に直面しています
ありがとう
問題は要約すると、最小の合計を持つ MxN 行列の KxK サブブロックを見つけます。この問題は、積分変換を使用して効率的に (入力のサイズに比例して) 解決できます。もちろん、これは必ずしも動的プログラミングの問題に役立つとは限りません。このソリューションが動的プログラミングの定式化と同等であるかどうかはわかりません....
とにかく(a,b)、元の行列のインデックス ペアごとMに、「積分変換」行列を計算しますI[a,b] = sum[i<=a, j<=b](M[i,j])。これは、前の行/列から計算された値を参照して、行列を順番にトラバースすることで計算できます。(少し考えれば、スパース行列を使ってこれを効率的に行うこともできます)
(a1..a2, b1..b2)次に、任意のサブブロックの合計をとして定数時間で計算できますI[a2,b2] - I[a1-1,b2] - I[a2,b1-1] + I[a1-1,b1-1]。すべての KxK サブブロックを反復して最小の合計を見つけるには、元の行列のサイズに比例して時間がかかります。
元の問題は整数座標のリストとして表現されているため (そして、おそらく、タワーの位置が整数座標ペアとして出力されることを期待している)、効率的なソリューションのために、フィールドを疎行列として表現する必要がある可能性があります。ツリーの座標を辞書順で並べ替える必要があります (たとえば、最初にx-coordinate で、次にy-coordinate で)。この並べ替えステップは size の入力を必要とする場合がO(L log L)あり、入力のサイズLのみを受け取る次のステップを支配することに注意してくださいO(L)。
また、「塔の端に一致する木が根こそぎにされる…」という問題により、端の長さが K の塔は実際には(K+1)x(K+1)サブブロックに対応します。