草庐IT

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

coder 2024-02-12 原文

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

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

这是链接:http://www.e-olymp.com/en/problems/18

最佳答案

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

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

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

现在我们仍然遇到像 1 7 这样的测试用例的问题。正确答案是 14，但您的程序回答 16。原因是您不允许重叠插入:从大小为 1x2 的矩形开始，我们可以使用序列选择、复制、插入+移动、插入+移动，插入+移动，插入+移动得到一个大小为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，它通过了所有测试用例。

关于c++ - 找到填充矩形的最少 MS Paint 操作数，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/31711278/

ampPaintpaintbcodepaintac++algorithmdynamic-programming

有关c++ - 找到填充矩形的最少 MS Paint 操作数的更多相关文章

  1. ruby - 什么是填充的 Base64 编码字符串以及如何在 ruby​​ 中生成它们？ - 2

    我正在使用的第三方API的文档状态:"[O]urAPIonlyacceptspaddedBase64encodedstrings."什么是“填充的Base64编码字符串”以及如何在Ruby中生成它们。下面的代码是我第一次尝试创建转换为Base64的JSON格式数据。xa=Base64.encode64(a.to_json) 最佳答案 他们说的padding其实就是Base64本身的一部分。它是末尾的“=”和“==”。Base64将3个字节的数据包编码为4个编码字符。所以如果你的输入数据有长度n和n%3=1=>"=="末尾用于填充n%

  2. ruby-on-rails - 如何优雅地重启 thin + nginx？ - 2

    我的瘦服务器配置了nginx，我的ROR应用程序正在它们上运行。在我发布代码更新时运行thinrestart会给我的应用程序带来一些停机时间。我试图弄清楚如何优雅地重启正在运行的Thin实例，但找不到好的解决方案。有没有人能做到这一点？ 最佳答案 #Restartjustthethinserverdescribedbythatconfigsudothin-C/etc/thin/mysite.ymlrestartNginx将继续运行并代理请求。如果您将Nginx设置为使用多个上游服务器，例如server{listen80;server

  3. ruby - 匹配大写字母并用后续字母填充，直到一定的字符串长度 - 2

    我有一个驼峰式字符串，例如:JustAString。我想按照以下规则形成长度为4的字符串:抓取所有大写字母；如果超过4个大写字母，只保留前4个；如果少于4个大写字母，则将最后大写字母后的字母大写并添加字母，直到长度变为4。以下是可能发生的3种情况:ThisIsMyString将产生TIMS(大写字母)；ThisIsOneVeryLongString将产生TIOV(前4个大写字母)；MyString将生成MSTR(大写字母+tr大写)。我设法用这个片段解决了前两种情况:str.scan(/[A-Z]/).first(4).join但是，我不太确定如何最好地修改上面的代码片段以处理最后一种

  4. ruby-on-rails - capybara ::ElementNotFound:无法找到 xpath "/html" - 2

    我正在学习http://ruby.railstutorial.org/chapters/static-pages上的RubyonRails教程并遇到以下错误StaticPagesHomepageshouldhavethecontent'SampleApp'Failure/Error:page.shouldhave_content('SampleApp')Capybara::ElementNotFound:Unabletofindxpath"/html"#(eval):2:in`text'#./spec/requests/static_pages_spec.rb:7:in`(root)'

  5. ruby - 使用 `+=` 和 `send` 方法 - 2

    如何将send与+=一起使用？a=20;a.send"+=",10undefinedmethod`+='for20:Fixnuma=20;a+=10=>30 最佳答案 恐怕你不能。+=不是方法，而是语法糖。参见http://www.ruby-doc.org/docs/ProgrammingRuby/html/tut_expressions.html它说Incommonwithmanyotherlanguages,Rubyhasasyntacticshortcut:a=a+2maybewrittenasa+=2.你能做的最好的事情是:

  6. ruby - 如何找到调用当前方法的方法 - 2

    如何找到调用此方法的位置？defto_xml(options={})binding.pryoptions=options.to_hifoptions&&options.respond_to?(:to_h)serializable_hash(options).to_xml(options)end 最佳答案 键入caller。这将返回当前调用堆栈。文档:Kernel#caller.例子[0]%rspecspec10/16|===================================================62=====

  7. ruby - 如何计算 Liquid 中的变量 +1 - 2

    我对如何计算通过{%assignvar=0%}赋值的变量加一完全感到困惑。这应该是最简单的任务。到目前为止，这是我尝试过的:{%assignamount=0%}{%forvariantinproduct.variants%}{%assignamount=amount+1%}{%endfor%}Amount:{{amount}}结果总是0。也许我忽略了一些明显的东西。也许有更好的方法。我想要存档的只是获取运行的迭代次数。 最佳答案 因为{{incrementamount}}将输出您的变量值并且不会影响{%assign%}定义的变量，我

  8. ruby - 如何使用 Selenium Webdriver 根据 div 的内容执行操作？ - 2

    我有一个使用SeleniumWebdriver和Nokogiri的Ruby应用程序。我想选择一个类，然后对于那个类对应的每个div，我想根据div的内容执行一个Action。例如，我正在解析以下页面:https://www.google.com/webhp?sourceid=chrome-instant&ion=1&espv=2&ie=UTF-8#q=puppies这是一个搜索结果页面，我正在寻找描述中包含“Adoption”一词的第一个结果。因此机器人应该寻找带有className:"result"的div，对于每个检查它的.descriptiondiv是否包含单词“adoption

  9. ruby-on-rails - 如何处理 Grape 中特定操作的过滤器之前？ - 2

    我正在我的Rails项目中安装Grape以构建RESTfulAPI。现在一些端点的操作需要身份验证，而另一些则不需要身份验证。例如，我有users端点，看起来像这样:moduleBackendmoduleV1classUsers现在如您所见，除了password/forget之外的所有操作都需要用户登录/验证。创建一个新的端点也没有意义，比如passwords并且只是删除password/forget从逻辑上讲，这个端点应该与用户资源。问题是Grapebefore过滤器没有像except,only这样的选项，我可以在其中说对某些操作应用过滤器。您通常如何干净利落地处理这种情况？

  10. ruby-on-rails - 在 Ruby on Rails 中发送响应之前如何等待多个异步操作完成？ - 2

    在我做的一些网络开发中，我有多个操作开始，比如对外部API的GET请求，我希望它们同时开始，因为一个不依赖另一个的结果。我希望事情能够在后台运行。我找到了concurrent-rubylibrary这似乎运作良好。通过将其混合到您创建的类中，该类的方法具有在后台线程上运行的异步版本。这导致我编写如下代码，其中FirstAsyncWorker和SecondAsyncWorker是我编写的类，我在其中混合了Concurrent::Async模块，并编写了一个名为“work”的方法来发送HTTP请求:defindexop1_result=FirstAsyncWorker.new.async.

随机推荐