7

के साथ कुछ लंबाई के बढ़ते उप-अनुक्रमों की कुल संख्या को कैसे प्राप्त करें बाइनरी इंडेक्स ट्री (बीआईटी) के साथ कुछ लंबाई के बढ़ते उप-अनुक्रमों की कुल संख्या मुझे कैसे मिल सकती है?बाइनरी इंडेक्स ट्री (बीआईटी)

वास्तव में इस Spoj Online Judge

से एक समस्या है उदाहरण
मान लीजिए मैं एक सरणी 1,2,2,10

लंबाई 3 हैं 1,2,4 और 1,3,4

तो, इस सवाल का जवाब के उप दृश्यों में वृद्धि 2 है।

उत्तर

10

करते हैं:

dp[i, j] = number of increasing subsequences of length j that end at i 

एक आसान समाधान O(n^2 * k) में है:

for i = 1 to n do 
    dp[i, 1] = 1 

for i = 1 to n do 
    for j = 1 to i - 1 do 
    if array[i] > array[j] 
     for p = 2 to k do 
     dp[i, p] += dp[j, p - 1] 

जवाब dp[1, k] + dp[2, k] + ... + dp[n, k] है।

अब, यह काम करता है, लेकिन यह आपके दिए गए बाधाओं के लिए अक्षम है, क्योंकि n10000 तक जा सकता है। k काफी छोटा है, इसलिए हमें n से छुटकारा पाने के लिए एक रास्ता खोजने का प्रयास करना चाहिए।

चलिए एक और दृष्टिकोण आज़माएं। हमारे पास S भी है - हमारे सरणी में मानों पर ऊपरी सीमा। आइए इसके संबंध में एल्गोरिदम खोजने का प्रयास करें।

dp[i, j] = same as before 
num[i] = how many subsequences that end with i (element, not index this time) 
     have a certain length 

for i = 1 to n do 
    dp[i, 1] = 1 

for p = 2 to k do // for each length this time 
    num = {0} 

    for i = 2 to n do 
    // note: dp[1, p > 1] = 0 

    // how many that end with the previous element 
    // have length p - 1 
    num[ array[i - 1] ] += dp[i - 1, p - 1] 

    // append the current element to all those smaller than it 
    // that end an increasing subsequence of length p - 1, 
    // creating an increasing subsequence of length p 
    for j = 1 to array[i] - 1 do   
     dp[i, p] += num[j] 

इस जटिलता O(n * k * S) है, लेकिन हम काफी आसानी से O(n * k * log S) करने के लिए इसे कम कर सकते हैं। हमें केवल एक डेटा संरचना की आवश्यकता है जो हमें एक श्रेणी में तत्वों को कुशलतापूर्वक योग और अद्यतन करने देता है: segment trees, binary indexed trees आदि

+0

'ओ (एन * एन * के) 'दृष्टिकोण निश्चित रूप से समय सीमा समाप्त हो जाएगी (टीएलई)। इसके बजाय हमें इसे तेज बनाने के लिए बीआईटी या सेगमेंट ट्री का उपयोग करना चाहिए। –

+0

@mostafiz - हाँ, यही दूसरा दृष्टिकोण है। – IVlad

+1

आपका मतलब क्या है "num [i] = i (तत्व, इस समय इंडेक्स नहीं) के साथ कितने बाद के अंत होते हैं," क्या होगा यदि हमारे पास अलग-अलग इंडेक्स पर समान तत्व हों? – bicepjai

संबंधित मुद्दे