डीपी समस्या में सहायता

Question

मैं एसपीओजे (link) से किसी समस्या को हल करने का प्रयास कर रहा हूं, जिसे संक्षेप में इस प्रकार वर्णित किया जा सकता है: एन अंतराल को देखते हुए, प्रत्येक पूर्णांक शुरुआत और अंत के साथ, और अधिकतम समय के साथ अंत दिया जाता है (चलिए इसे max_end कहते हैं), आप कितने तरीकों से अंतराल का एक सेट चुन सकते हैं जो 1 को कवर करता है ... max_end। अंतराल ओवरलैप हो सकता है। मैंने एक डीपी की कोशिश की; अंत समय से पहले क्रमबद्ध करें, फिर डीपी [i] एक जोड़ी है, जहां डीपी [i]। सबसे पहले अंतराल की न्यूनतम संख्या 1 को कवर करने के लिए आवश्यक है ... अंत [i] अंतराल I और डीपी [i] .second यह करने के तरीकों की संख्या है। यहां मेरा मुख्य डीपी लूप है:

for(int i = 1; i < n; i ++) { 
    for(int j = 0; j < i; j ++) { 
     if(! (x[ j ].end >= x[ i ].start - 1)) 
      continue; 
     if(dp[ j ].first + 1 < dp[ i ].first) { 
      dp[ i ].first = dp[ j ].first + 1; 
      dp[ i ].second = dp[ j ].second; 
     } 
     else if(dp[ j ].first + 1 == dp[ i ].first) { 
      dp[ i ].second += dp[ j ].second; 
     } 
    } 
} 

दुर्भाग्यवश, यह काम नहीं किया। क्या कोई मुझे बता सकता है कि मुझे गलती कहाँ है? अग्रिम में धन्यवाद! :)

Answer 1

मुझे यकीन है कि मैं अपने समाधान विचार प्राप्त नहीं कर रहा हूँ, लेकिन मैं अपने एसी समाधान का वर्णन:

मैं याद के साथ समारोह का उपयोग कर रहा है, लेकिन आप यह गैर recurcive डी पी का उपयोग कर फिर से लिख सकते हैं।

मान लीजिए कि हम सरणी में हमारे अंतराल करते

इस जोड़ी को एक [100]; जहां एक [i]। पहला अंतराल शुरू होता है और एक [i] .second अंतराल अंत होता है।

इस सरणी को से पहले प्रारंभ करें (डिफ़ॉल्ट जोड़ी तुलनित्र के साथ एसएलएल सॉर्ट एल्गोरिदम का डिफ़ॉल्ट व्यवहार)।

अब कल्पना करें कि हम शुरुआत से अंत तक एक-एक करके अंतराल डाल रहे हैं।

चलो f (int x, int prev) भरने को समाप्त करने के तरीकों की संख्या वापस कर दें यदि वर्तमान अंतराल x है और पिछला 'पिछला' है।

हम इस प्रकार के रूप में यह गणना करेंगे:

int f(int x, int prev) { 
    // if already calculated dp[x][prev], return it. Otherwise, calculate it 
    if (dp[x][prev] != -1) { 
    return dp[x][prev]; 
    } 
    if (a[x].second == m) { 
    return dp[x][prev] = 1; // it means - X is last interval in day 
    } 
    else { 
    dp[x][prev] = 0; 
    for (int i = x + 1; i < n; ++i) { // try to select next interval 
     if (a[i].first <= a[x].second && // there must be not empty space after x interval 
      a[i].second > a[x].second && // if this is false, the set won't be minimal - i interval is useless 
      a[i].first > a[x].first && // if this is false, the set won't be minimal, x interval is useless 
      a[prev].second < a[i].first) { // if this is false, the set won't be minimal, x interval is useless. 
     dp[x][prev] = (dp[x][prev] + f(i, x)) % 100000000; 
     } 
    } 
    } 
    return dp[x][prev]; 
} 

उसके बाद हम जिनमें से पहले 0 पर शुरू और दूसरा पहले से जुड़ा हुआ है, अंतराल के हर जोड़ी के लिए इस समारोह कॉल करने की आवश्यकता:

for (int i = 0; i < n; ++i) { 
    if (a[i].first == 0) { 
    for (int j = i + 1; j < n; ++j) { 
     if (a[j].first > 0 && // we don't need to start at 0 - in this case either i or j will be useless 
      a[j].first <= a[i].second && // there must be no space after i interval 
      a[j].second > a[i].second) { // in opposite case j will be useless 
      res = (res + f(j, i)) % 100000000; 
     } 
    } 
    // also we need to check the case when we use only one interval: 
    if (a[i].second == m) { 
     res = (res + 1) % 100000000; 
    } 
    } 
} 

उसके बाद हमें केवल res को प्रिंट करने की आवश्यकता है।