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

Question

我在比赛的某个地方发现了这个问题,但还没有找到解决方案.

我可以在屏幕上的另一个地方"选择","复制","插入"和"移动".最初我有一个大小为1x1的矩形.我需要做的最少量的操作来构建另一个矩形,其大小是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;
}

这是链接: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、copy、insert+move、insert+move， insert+move，insert+move得到一个大小为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]i10001002

@@ -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;

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