c++ - 试图理解这个解决方案

Question

我试图解决一个问题，但遇到了一些未能解决的障碍，从这里开始的问题是:Codeforces - 817D

现在我尝试暴力破解它，对我可以生成的数组的每个部分使用基本的 get min 和 max，然后跟踪它们我减去它们并将它们加在一起以获得最终的不平衡，这看起来不错但是它给了我一个超出时间限制的原因，因为 n*(n+1)/2 给定 n 是 10^6 的数组的子段，所以我只是没能绕过它，并且在几个小时后没有得到任何新的想法我决定看一个解决方案，老实说我什么都不懂:/，这是解决方案:

#include <bits/stdc++.h>
#define ll long long    
int a[1000000], l[1000000], r[1000000];
    int main(void) {
        int i, j, n;
        scanf("%d",&n);
        for(i = 0; i < n; i++) scanf("%d",&a[i]);
        ll ans = 0;
        for(j = 0; j < 2; j++) {
            vector<pair<int,int>> v;
            v.push_back({-1,INF});
            for(i = 0; i < n; i++)  {
                while (v.back().second <= a[i]) v.pop_back();
                l[i] = v.back().first;
                v.push_back({i,a[i]});
            }
            v.clear();
            v.push_back({n,INF});
            for(i = n-1; i >= 0; i--)  {
                while (v.back().second < a[i]) v.pop_back();
                r[i] = v.back().first;
                v.push_back({i,a[i]});
            }
            for(i = 0; i < n; i++)  ans += (ll) a[i] * (i-l[i]) * (r[i]-i);
            for(i = 0; i < n; i++)  a[i] *= -1;
        }
        cout << ans;
    }

我试着追踪它，但我一直想知道为什么使用 vector ，我得到的唯一想法是他想将 vector 用作堆栈，因为它们的行为相同(几乎)，但事实是我不这样做甚至知道为什么我们在这里需要一个堆栈，这个等式 ans += (ll) a[i] * (i-l[i]) * (r[i]-i); 真的让我很困惑，因为我不明白它是从哪里来的。

Answer 1

好吧，这真是一头野兽般的计算。我必须承认，我也不完全理解。蛮力解决方案的问题是，您必须重新计算值或重新计算。

在稍作修改的示例中，您计算​​输入 2, 4, 1 的以下值(我按“距离”重新排序)

[2, *, *] (from index 0 to index 0), imbalance value is 0; i_min = 0, i_max = 0
[*, 4, *] (from index 1 to index 1), imbalance value is 0; i_min = 1, i_max = 1
[*, *, 1] (from index 2 to index 2), imbalance value is 0; i_min = 2, i_max = 2
[2, 4, *] (from index 0 to index 1), imbalance value is 2; i_min = 0, i_max = 1
[*, 4, 1] (from index 1 to index 2), imbalance value is 3; i_min = 2, i_max = 1
[2, 4, 1] (from index 0 to index 2), imbalance value is 3; i_min = 2, i_max = 1

where i_min and i_max are the indices of the element with the minimum and maximum value. 
For a better visual understanding, i wrote the complete array, but hid the unused values with *

所以在最后一个案例中 [2, 4, 1] , 蛮力寻找所有值的最小值，这不是必需的，因为您已经通过计算 [2,4] 计算了问题子空间的值。和 [4,1] .但是仅比较值是不够的，您还需要跟踪最小和最大元素的索引，因为这些可以在下一步计算 [2, 4, 1] 时重复使用。 .

这背后的想法是一个叫做dynamic programming的概念。 ，其中存储计算结果以供再次使用。通常，您必须在速度和内存消耗之间做出选择。

所以回到你的问题，这是我的理解:

• 数组 l和 r用于存储当前索引左边或右边最大数的索引
• vector v用于查找大于当前数字 ( a[i] ) 的最后一个数字(及其索引)。它跟踪上升的数字系列，例如对于输入 5,3,4一开始是5被存储，那么 3当4来了，弹出 3 但需要 5 的索引(存储在 l[2] 中)
• 然后是这个奇特的计算(ans += (ll) a[i] * (i-l[i]) * (r[i]-i))。最大(在第二次运行中最小)元素的存储索引与值 a[i] 一起计算。现在这对我来说意义不大，但似乎有效(抱歉)。
• 最后，数组中的所有值a乘以 -1 ，这意味着旧的最大值现在是最小值，并且再次进行计算(在 j 上的第 2 次外部 for 循环运行)

这最后一步(将 a 乘以 -1 )和 j 上的外部 for 循环不是必需的，但它是重用代码的一种优雅方式。

希望对您有所帮助。