找到填充矩形的最少 MS Paint 操作数

Question

我在比赛的某个地方发现了这个问题，但还没能想出解决办法。

I can "select", "copy", "insert" and "move" in another place a figures on the screen. Initially I have the rectangle with size 1x1. What the least quantity of these operations I have to do for building of another rectangle, which size is AxB.

这是我的错误代码：

#include <iostream>
#include <cmath>
#define size 1002
using namespace std;

int main()
{
    int painta[size];
    int paintb[size];
    int i,j,a,b,temp;

    cin >> a >> b;
    if (a>b)
    {
        temp=a;
        a=b;
        b=temp;
    }

    painta[1]=4;
    for (i=2; i<=a; i++)
        painta[i]=painta[i-1]+2;

    for (i=2; i<=a; i++)
    {
        painta[2*i]=min(painta[i]+4,painta[2*i]);
        for (j=3*i; j<=a; j+=i)
        {
            painta[j]=min(painta[j-i]+2,painta[j]);
        }
    }

    paintb[1]=painta[a];
    paintb[2]=paintb[1]+4;

    for (i=3; i<=b; i++)
        paintb[i]=paintb[i-1]+2;

    for (i=2; i<=b; i++)
    {
        paintb[2*i] = min(paintb[i]+4,paintb[2*i]);
        for (j=3*i; j<=b; j+=i)
        {
            paintb[j]=min(paintb[j-i]+2,paintb[j]);
        }
    }
    cout << paintb[b] << endl;
    return 0;
}

这里是link：http://www.e-olymp.com/en/problems/18

Answer 1

你的方法没问题，虽然你犯了一些实施错误，你可以通过检查一些小的测试用例来发现这些错误。

例如，一个失败的测试用例是 1 2，您的程序给出答案 8，尽管 6 是正确的。这是因为您应该使用 a > b 而不是 b > a 来让您的算法工作：

-    if (a>b)
+    if (a<b)

现在我们仍然遇到像 1 7 这样的测试用例的问题。正确答案是 14，但你的程序回答了 16。原因是你不允许重叠插入：从一个大小为 1x2 的矩形开始，我们可以使用序列 select，复制，插入+移动，插入+移动，插入+移动，插入+移动得到一个大小为1x7的矩形。考虑到这只会使程序稍微复杂一些：

@@ -24,9 +24,10 @@
     for (i=2; i<=a; i++)
     {
         painta[2*i]=min(painta[i]+4,painta[2*i]);
-        for (j=3*i; j<=a; j+=i)
+        for (j=2*i+1; j<=a; j++)
         {
-            painta[j]=min(painta[j-i]+2,painta[j]);
+            int steps = (j - i - 1) / i;
+            painta[j]=min(painta[2*i]+2*steps,painta[j]);
         }
     }

@@ -39,9 +40,10 @@
     for (i=2; i<=b; i++)
     {
         paintb[2*i] = min(paintb[i]+4,paintb[2*i]);
-        for (j=3*i; j<=b; j+=i)
+        for (j=2*i+1; j<=b; j++)
         {
-            paintb[j]=min(paintb[j-i]+2,paintb[j]);
+            int steps = (j - i - 1) / i;
+            paintb[j]=min(paintb[2*i]+2*steps,paintb[j]);
         }
     }

现在这里仍然有一个小溢出，可能会导致程序因大输入而崩溃：您正在循环内访问 painta[2*i] 和 paintb[2*i]。 i 最大可达 1000，但数组只有 1002 大小。很容易修复：

@@ -5,12 +5,12 @@

 int main()
 {
-    int painta[size];
-    int paintb[size];
+    int painta[size*2];
+    int paintb[size*2];
     int i,j,a,b,temp;

Et voila，它通过了所有测试用例。

找到填充矩形的最少 MS Paint 操作数

Find the minimum number of MS Paint operations to fill a rectangle

c++

algorithm

dynamic-programming