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

Question

我试过了 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;
}

Answer 1

这是一个可以使 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 中最大值的三角形。