ऑप्टिमाइज़ करें: लंबाई के निरंतर बाद में किसी सरणी को विभाजित करें जैसे प्रत्येक अनुक्रम का अधिकतम मूल्य न्यूनतम

Question

पर O(n^2) एल्गोरिदम अनुकूलित करें।

समस्या वक्तव्य

को देखते हुए n धनात्मक पूर्णांक की सरणी A। सरणी को k से अधिक लंबाई के निरंतर बाद में विभाजित करें, जैसे कि प्रत्येक अनुवर्तीता का अधिकतम मूल्य न्यूनतम है। यहां एक उदाहरण दिया गया है।

यदि n = 8 और k = 5 और सरणी के तत्व 1 4 1 3 4 7 2 2 हैं, तो सर्वोत्तम समाधान 1 | 4 1 3 4 7 | 2 2 है। योग max{1} + max{4, 1, 3, 4, 7} + max{2, 2} = 1 + 7 + 2 = 10 होगा।

O (n^2) समाधान

dp[i] subproblem सरणी A[0] ... A[i] के लिए समस्या बयान में के रूप में कम से कम राशि होने दो। dp[0] = A[0] और, 0 < i < n (dp[-1] = 0), के लिए

// A, n, k, - defined 
// dp - all initialized to INF 
dp[0] = A[0]; 
for (auto i = 1; i < n; i++) { 
    auto max = -INF; 
    for (auto j = i; j >= 0 && j >= i-k+1; j--) { 
     if (A[j] > max) 
      max = A[j]; 
     auto sum = max + (j > 0 ? dp[j-1] : 0); 
     if (sum < dp[i]) 
      dp[i] = sum; 
    } 
} 
// answer: dp[n-1] 

O (n लॉग ऑन एन)?

समस्या लेखक ने दावा किया कि O(n log n) समय में इसे हल करना संभव था, और कुछ ऐसे लोग हैं जो परीक्षण के मामलों को पारित करने में सक्षम थे। इसे कैसे अनुकूलित किया जा सकता है?

Answer 1

नोट: मैं थोड़ा गतिशील प्रोग्रामिंग संबंध बदल रहा हूं, ताकि j = 0 पर कोई विशेष मामला न हो।

dp[i] = min(dp[j] + max(A[j], ..., A[i-1]), i-k <= j < i)

समस्या का जवाब अब dp[n] है: अब dp[j] पहले j शर्तों A[0], ..., A[j-1] और के लिए जवाब है।

---

सूचना है कि अगर j < i और dp[j] >= dp[i], तो आपको निम्न संक्रमण में dp[j] की जरूरत नहीं होगी, क्योंकि max(A[j], ..., A[l]) >= max(A[i], ..., A[l]) (इसलिए यह हमेशा बेहतर होगा j के बजाय i में कटौती करने के लिए।

इसके अलावा C[j] = max(A[j+1], ..., A[l]) जाने (जहां l गतिशील प्रोग्रामिंग चरण में हमारी वर्तमान अनुक्रमणिका है, यानी i आपके सी ++ प्रोग्राम में)

फिर आप स्मृति में कुछ सेट्स को याद रख सकते हैं x1 < ... < xm (आपके गतिशील प्रोग्रामिंग संबंध के संक्रमण के लिए "दिलचस्प" सूचकांक) जैसे कि: dp[x1] < ... < dp[xm] (1)। फिर स्वचालित रूप से C[x1] >= ... >= C[xm] (2)।

• पॉप वापस (जब हम i+1 करने के लिए i से ले जाते हैं, हम कहना होगा कि i-k अब तक नहीं पहुंचा जा) या सामने (सीएफ:

  {x1, ..., xm} संग्रहीत करने के लिए, हम कुछ डेटा संरचना है कि निम्नलिखित कार्यों का समर्थन करता है की जरूरत है प्रविष्टि)।

• पुश फ्रंट x (जब हमने dp[i] की गणना की है, तो हम संबंधित तत्वों को हटाकर (1) को संरक्षित करते समय इसे सम्मिलित करते हैं)।
• गणना min(dp[xj] + C[xj], 1 <= j <= m)।

इस प्रकार कुछ कतार स्टोर करने के लिए सभी dp[xi] + C[xi] पर्याप्त होगी एक set के साथ एक साथ x1, ..., xk स्टोर करने के लिए।

---

हम दोनों कैसे सुरक्षित करूं (1) और C अद्यतन जब हम एक तत्व i डालने?

• कंप्यूटिंग dp[i] से पहले, हम A[i-1] साथ C अद्यतन करें। इसके लिए हमें सेट x s.t में सबसे छोटा तत्व xj मिलता है। C[xj] <= A[i-1]। फिर (1) और (2) dp[j'] + C[j'] >= dp[j] + C[j] सभी j' >= j के लिए इंगित करें, इसलिए हम C[xj]A[i-1] पर अपडेट करते हैं और हम सेट (*) से x(j+1), ..., xm हटाते हैं।
• जब हम dp[i] डालते हैं, तो हम बस सभी तत्वों को हटाते हैं s.t. आगे बढ़कर dp[j] >= dp[i]।
• जब हम i-k हटाते हैं, तो यह संभव हो सकता है कि (*) में नष्ट कुछ तत्व अब सबसे अच्छा हो रहा है। तो यदि आवश्यक हो तो हम C अपडेट करें और अंतिम तत्व डालें।

जटिलता: O(n log n) (सेट में 2n सम्मिलन में हो सकता है)।

इस कोड का सार मुख्य विचारों:

template<class T> void relaxmax(T& r, T v) { r = max(r, v); } 

vector<int> dp(n + 1); 
vector<int> C(n + 1, -INF); 
vector<int> q(n + 1); 
vector<int> ne(n + 1, -INF); 
int qback = 0, qfront = 0; 
auto cmp = [&](const int& x, const int& y) { 
    int vx = dp[x] + C[x], vy = dp[y] + C[y]; 
    return vx != vy ? vx < vy : x < y; 
}; 
set<int, decltype(cmp)> s(cmp); 

dp[0] = 0; 
s.insert(0); 
q[qfront++] = 0; 

for (int i = 1; i <= n; ++i) { 
    C[i] = A[i - 1]; 
    auto it_last = lower_bound(q.begin() + qback, q.begin() + qfront, i, [=](const int& x, const int& y) { 
     return C[x] > C[y]; 
    }); 

    for (auto it = it_last; it != q.begin() + qfront; ++it) { 
     s.erase(*it); 
     C[*it] = A[i - 1]; 
     ne[*it] = i; 
     if (it == it_last) s.insert(*it); 
    } 

    dp[i] = dp[*s.begin()] + C[*s.begin()]; 

    while (qback < qfront && dp[q[qfront]] >= dp[i]) { 
     s.erase(q[qfront]); 
     qfront--; 
    } 

    q[qfront++] = i; 
    C[i] = -INF; 
    s.insert(i); 

    if (q[qback] == i - k) { 
     s.erase(i - k); 

     if (qback + 1 != qfront && ne[q[qback]] > q[qback + 1]) { 
      s.erase(q[qback + 1]); 
      relaxmax(C[q[qback + 1]], C[i - k]); 
      s.insert(q[qback + 1]); 
     } 

     qback++; 
    } 
} 

// answer: dp[n] 

इस बार मैं अपने एल्गोरिथ्म के खिलाफ यह तनाव परीक्षण: see here।

कृपया मुझे बताएं कि यह अभी भी अस्पष्ट है।