1

私はいくつかのプログラミング コンテストの質問を練習してきました (今後のコンテストの楽しみと練習のため)。

どこから始めればよいかよくわかりません=/。この問題を解決するには、どのようにアプローチすればよいですか?

4

4 に答える 4

1

私には動的計画法の問題のように見えます

  • F（w、h）を、wxhの長方形を並べて表示する正方形の最小数とします。

  • Fの再帰的定式化を見つけます。

    • w=0またはh=0の場合、F（w、h）= 0

    • それ以外の場合、F（w、h）=

      For each allowable size a=i^2 <= min(w,h), try to place the a by a square (A)
 in the top left corner.
One of the following possibilities will describe the
 optimal solution:
 +---+--+    +---+--+
 | A | C|    | A |  |
 +---+--+    +---+  |
 |  B   |    |B  |C |
 +------+    +---+--+
 So, choose the best of
   (1 + F(h-a, w) + F(h-a, w-a)) or
   (1 + F(h-a, a) + F(w-a, h))

ナプキンでbig-O分析を行うと、これは-O(side^2 * sqrt(side))っぽいアルゴリズムのようです。これが多すぎる場合は、次のことができます。

  • 問題の対称性を利用してみてください（F（w、h）= F（h、w）など）
  • 分析をもう一度チェックして、分析が遅すぎて別のアルゴリズムが必要であることを確認します（おそらく、すべての（w、h）ペアについて計算する必要はありませんか？）
  • より単純で、あまり説得力のない戦略を可能にする問題のいくつかの特性を見つけてください。（たとえば、可能な限り最大の正方形を選択することは、単純な欲張り戦略です...しかし、それはすべての場合に機能しますか？）
于 2011-04-03T04:40:47.643 に答える
0

あなたを覚えている「1、2、4、8など」は何ですか?

図を見てください。あなたが選択するフィリングの順序（サイズの観点から）は何ですか？

于 2011-04-03T04:03:18.927 に答える
0

手で答えを考え出すことから始めて、半ダース程度と言います...次に、プログラムで問題をどのように解決したかをモデル化します...そして、機能する「ブルートフォース」の答えが得られたら、さらに問題を解決してみてくださいエレガントに。

この問題は、最初に最大サイズのタイルをできるだけ多く配置してから、次に収まる最大サイズで可能な場所を埋めることから始めます。それから小さくなります...いっぱいになるまで。

配列または配列を使用して、埋められたスペースを空間的に追跡することができます...ただし、次元を取得して2つのうち小さい方を取得し、ログを利用するなど、いくつかの簡単な計算を介してこれを行う簡単な方法があると思いますベース2またはそのようなもの...

私は素敵なきちんとした再帰的な解決策があると確信しています..2のべき乗に基づいて..それから非再帰的な解決策にそれを解明することができます...

于 2011-04-03T04:05:24.667 に答える