試圖瞭解這個解決方案

我試圖解決一個問題，我進入我沒能解決一些障礙，在這裏出發是問題：Codeforces - 817D 試圖瞭解這個解決方案

現在我試圖蠻力它，使用基本得到我可以生成的數組中的每個段的最小值和最大值，然後跟蹤它們我將它們相減並將它們加在一起以獲得最終的不平衡，這看起來不錯，但它給了我一個超出時間限制的原因暴力強制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; 
    }

我試圖追蹤它，但我一直想知道爲什麼是矢量使用，我得到的唯一想法是他想使用向量作爲一個堆棧，因爲他們都行爲相同（幾乎），但然後事實，我不甚至不知道爲什麼我們需要一個堆棧，而這個等式ans += (ll) a[i] * (i-l[i]) * (r[i]-i);真的令我困惑，因爲我不知道它從哪裏來。

來源

2017-06-16 Biggie

那麼這是一個計算的野獸。我必須承認，我也不完全理解它。暴力解決方案的問題是，你必須重新計算值或重新整理。

在稍微修改的例子中，你計算的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]，蠻力查找最小值（i加「距離」重新排序它）值，因爲您已經通過計算[2,4]和[4,1]來計算問題的子空間的值，所以這不是必需的。但僅比較這些值是不夠的，還需要跟蹤最小和最大元素的索引，因爲在計算[2, 4, 1]時，可以在下一步中重新使用這些索引。

這背後的理念是一個名爲dynamic programming的概念，其中來自計算的結果被存儲以再次使用。通常，您必須在速度和內存消耗之間進行選擇。

所以要回到你的問題，這裏是我的理解：

陣列l和r用於存儲當前的
矢量留下的最大數量或右的索引v用於查找大於當前值的最後一個數字（及其索引）（a[i]）。它跟蹤上升的號碼系列，例如在第一所述5輸入5,3,4被存儲，則3並且當4到來時，3被彈出，但需要的5的索引（存儲在l[2]）
再有就是這個花式計算（ans += (ll) a[i] * (i-l[i]) * (r[i]-i)）。存儲的最大值（以及第二次運行中的最小值）索引與價值a[i]一起計算，這對我而言現在沒有多大意義，但似乎可行（對不起）。
最後，陣列a中的所有值由-1，這意味着，老最大值現在是最低要求，並且計算完成再次相乘（第二外的運行for循環在j）的

最後一步（乘以a,-1）和外部for循環j不是必需的，但它是重用代碼的一種優雅方式。

希望這會有所幫助。

來源

2017-06-16 13:08:10 AquilaRapax

一個提高複雜度的小技巧，不要做單個元素集。然而他們的不平衡值是零。 –

是的，你是對的。但是，這確實會影響「真實」世界的執行時間，但並不會改變時間複雜度。 – AquilaRapax

試圖瞭解這個解決方案

回答

相關問題