草庐IT

c++ - 子三角形中最大元素的总和

coder 2024-02-05 原文

我试过了 last question来自今年的 CCC 2019 S5。

问题陈述:

在平行宇宙中，计算机科学中最重要的数据结构是三角形。大小为 M 的三角形由 M 行组成，第 i 行包含 i 个元素。此外，这些行必须排列成等边三角形的形状。也就是说，每一行都以通过三角形中间的垂直对称线为中心。例如，下图显示了一个大小为 4 的三角形:

一个三角形包含子三角形。例如，上面的三角形包含十个大小为1的子三角形，六个大小为2的子三角形(其中两个是包含(3,1,2)的三角形和包含(4,6,1)的三角形)，三个大小为 3 的子三角形(其中一个包含 (2,2,1,1,4,2))。请注意，每个三角形都是其自身的子三角形。

给定一个大小为 N 的三角形，并且必须找到大小为 K 的每个子三角形的最大元素之和。

输入规范

第一行包含两个用空格分隔的整数N和K(1≤K≤N≤3000)。

接下来是 N 行描述三角形。其中第i行包含i个空格分隔的整数ai,j(0≤ai,j≤10^9)，代表三角形的第i行。

对于 15 个可用标记中的 4 个，N≤1000。

输出规范

输出每个大小为K的子三角形的最大元素的整数和。

示例输入

4 2
3
1 2
4 2 1
6 1 4 2

样本输入的输出

23

不幸的是，我的解决方案给出了 TLE 结论，我不知道如何优化它。

这道题基本上是求子三角形的最大元素并将它们相加。我的方法很简单，我迭代大三角形的每个元素，使它们成为子三角形的“根”，然后我尝试去它的每个元素找到最大值并将它们添加到结果中。

我需要一些帮助来改进我的解决方案，它需要一些数据结构吗？

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    vector<vector<int>> triangle;

    int n;
    int k;

    cin >> n >> k;

    for (int i = 0; i < n; ++i)
    {
        triangle.push_back(vector<int>(i + 1, 0));

        for (int j = 0; j <= i; ++j)
            cin >> triangle[i][j];
    }

    int sum = 0;

    for (int level = 0; level <= n - k; ++level)
        for (int root = 0, size1 = triangle[level].size(); root < size1; ++root)
        {
            int largest = 0;

            for (int i = level, counter = 0; i < level + k; ++i, ++counter)
                for (int j = root, times = 0, size2 = triangle[i].size(); j < size2 && times <= counter; ++j, ++times)
                    largest = max(largest, triangle[i][j]);

            sum += largest;
        }

    cout << sum << "\n";

    return 0;
}

最佳答案

这是一个可以使 O(n^2 log(k)) 的解决方案，它足够快。

思路是这样的。从大小为 1 的三角形的 nxn 三角形到大小为 2 的三角形的最大值的 (n-1)x(n-1) 三角形是一个 O(n) 操作。只需将每个三角形与其相邻三角形的最大值进行比较即可。

同样的技巧可以用于从第二个三角形到 (n-2)x(n-2) 大小为 2 的三角形。但是如果你在每个三角形中跳过一个方向，您可以直接到达大小为 4 的三角形中最大值的 (n-3)x(n-3) 三角形。同样在时间上 O(n) .为了说明后者，假设我们开始于:

    2
   3 1
  1 2 4
 4 2 1 5
6 1 4 2 3

为了得到大小为 2 的三角形，我们将每个三角形与其相邻三角形进行比较。

   3
  3 4
 4 2 5
6 4 4 5

为了得到大小为 4 的三角形比较跳过一个，所以我们比较底部的一个 6、3、4。下一个我们比较 4、4、5 等等。获得:

 5
6 5

然后我们将它们加在一起得到 11。

接下来，从 (n-3)x(n-3) triangle of maximum values in triangles of size 4 可以直接转到 triangle of maximum values in triangles of sizes 5， 6、7 或 8，通过选择我们接下来要比较的三角形的大小，跳过 1、跳过 2 或跳过 3。

依此类推导致 O(log(k)) 步骤，通过 k 个三角形获得 k 中最大值的三角形。

关于c++ - 子三角形中最大元素的总和，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/55253790/

amp43codetriangle三角形c++algorithmoptimization

有关c++ - 子三角形中最大元素的总和的更多相关文章

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

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

  2. ruby - 在哈希的键数组中追加元素 - 2

    查看我的Ruby代码:h=Hash.new([])h[0]=:word1h[1]=h[1]输出是:Hash={0=>:word1,1=>[:word2,:word3],2=>[:word2,:word3]}我希望有Hash={0=>:word1,1=>[:word2],2=>[:word3]}为什么要附加第二个哈希元素(数组)？如何将新数组元素附加到第三个哈希元素？ 最佳答案 如果您提供单个值作为Hash.new的参数(例如Hash.new([])，完全相同的对象将用作每个缺失键的默认值。这就是您所拥有的，那是你不想要的。您可以改用

  3. 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.你能做的最好的事情是:

  4. 「Python｜Selenium｜场景案例」如何定位iframe中的元素？ - 2

    本文主要介绍在使用Selenium进行自动化测试或者任务时，对于使用了iframe的页面，如何定位iframe中的元素文章目录场景描述解决方案具体代码场景描述当我们在使用Selenium进行自动化测试的时候，可能会遇到一些界面或者窗体是使用HTML的iframe标签进行承载的。对于iframe中的标签，如果直接查找是无法找到的，会抛出没有找到元素的异常。比如近在咫尺的例子就是，CSDN的登录窗体就是使用的iframe，大家可以尝试通过F12开发者模式查看到的tag_name,class_name,id或者xpath来定位中的页面元素，会抛出NoSuchElementException异常。解决

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

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

  6. ruby - Hanami link_to 助手只呈现最后一个元素 - 2

    我是HanamiWorld的新人。我已经写了这段代码:moduleWeb::Views::HomeclassIndexincludeWeb::ViewincludeHanami::Helpers::HtmlHelperdeftitlehtml.headerdoh1'Testsearchengine',id:'title'hrdiv(id:'test')dolink_to('Home',"/",class:'mnu_orizontal')link_to('About',"/",class:'mnu_orizontal')endendendendend我在模板上调用了title方法。htm

  7. ruby - 将n维数组的每个元素乘以Ruby中的数字 - 2

    在Ruby中，是否有一种简单的方法可以将n维数组中的每个元素乘以一个数字？这样:[1,2,3,4,5].multiplied_by2==[2,4,6,8,10]和[[1,2,3],[1,2,3]].multiplied_by2==[[2,4,6],[2,4,6]]？(很明显，我编写了multiplied_by函数以区别于*，它似乎连接了数组的多个副本，不幸的是这不是我需要的)。谢谢! 最佳答案 它的长格式等价物是:[1,2,3,4,5].collect{|n|n*2}其实并没有那么复杂。你总是可以使你的multiply_by方法:c

  8. ruby-on-rails - 需要帮助最大化多个相似对象中的 3 个因素并适当排序 - 2

    我需要用任何语言编写一个算法，根据3个因素对数组进行排序。我以度假村为例(如Hipmunk)。假设我想去度假。我想要最便宜的地方、最好的评论和最多的景点。但是，显然我找不到在所有3个中都排名第一的方法。Example(assumingthereare20importantattractions):ResortA:$150/night...98/100infavorablereviews...18of20attractionsResortB:$99/night...85/100infavorablereviews...12of20attractionsResortC:$120/night

  9. arrays - 计算数组中的匹配元素 - 2

    给定两个大小相等的数组，如何找到不考虑位置的匹配元素的数量？例如:[0,0,5]和[0,5,5]将返回2的匹配项，因为有一个0和一个5共同；[1,0,0,3]和[0,0,1,4]将返回3的匹配项，因为0有两场，1有一场；[1,2,2,3]和[1,2,3,4]将返回3的匹配项。我尝试了很多想法，但它们都变得相当粗糙和令人费解。我猜想有一些不错的Ruby习惯用法，或者可能是一个正则表达式，可以很好地回答这个解决方案。 最佳答案 您可以使用count完成它:a.count{|e|index=b.index(e)andb.delete_at

  10. arrays - Ruby 数组 += vs 推送 - 2

    我有一个数组数组，想将元素附加到子数组。+=做我想做的，但我想了解为什么push不做。我期望的行为(并与+=一起工作):b=Array.new(3,[])b[0]+=["apple"]b[1]+=["orange"]b[2]+=["frog"]b=>[["苹果"],["橙子"],["Frog"]]通过推送，我将推送的元素附加到每个子数组(为什么？):a=Array.new(3,[])a[0].push("apple")a[1].push("orange")a[2].push("frog")a=>[[“苹果”、“橙子”、“Frog”]、[“苹果”、“橙子”、“Frog”]、[“苹果”、“

随机推荐