子三角形中的最大元素总数

Question

我尝试了今年CCC 2019 S5的最后一个问题。

问题陈述：

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

三角形包含子三角形。例如，上面的三角形包含10个大小为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判决，而且我不知道如何优化它。

这个问题基本上要求找到子三角形的最大元素并将它们加在一起。我的方法很简单，我迭代了大三角形的每个元素，使它们成为子三角形的“根”，然后尝试转到它的每个元素以找到max并将它们添加到结果中。

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

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

Answer 1

O(n^2 log(k))这是一个可以足够快地制定的解决方案。

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

可以使用相同的技巧从第二个三角形转到(n-2)x(n-2)大小为 2 的三角形的三角形。但是，如果您在每个方向上跳过一个三角形，则可以直接到达(n-3)x(n-3)大小为 4 的三角形中的最大值的三角形。同样及时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)大小为 4 的三角形中的最大值三角形，您可以通过选择我们接下来要比较的三角形的大小，直接转到大小为 5、6、7 或 8 的三角形中的最大值三角形，跳过 1、跳过 2 或跳过 3。

依此类推，从而产生通过三角形O(log(k))获得最大值的三角形的步骤。kk