उप-खंड गतिशीलता: बुनियादी चीजें और "एक अच्छा है और दो बेहतर है"

शुभ संध्या

इस पोस्ट में मैं सेंट पीटर्सबर्ग में शहर के कंप्यूटर विज्ञान ओलंपियाड के व्यावहारिक दौरे से समस्या बी "ओक्स" का विश्लेषण करूंगा।

उप-खंडों द्वारा गतिशील प्रोग्रामिंग के लिए यह समस्या और एक समाधान का विचार दिलचस्प है कि एक के बजाय दो वक्ताओं को गिनना अधिक सुविधाजनक है। यदि आप रुचि रखते हैं (गतिशीलता की अनदेखी जारी नहीं करती है, लेकिन यह अधिक कठिन होगा) - स्वागत है।

शर्त

शुरुआत के लिए, आप समस्या की स्थिति देख सकते हैं। यह यहाँ परीक्षणों के साथ स्थित है (केवल शर्तों को min.us से डाउनलोड किया जा सकता है)।

किंवदंती को मोड़ने के बाद, निम्न कार्य शेष है:

• N (2 <= n <= 200) ओक हैं, प्रत्येक की ऊंचाई है - 1 से 1000 तक एक पूर्णांक (incl।)।
• हम कर सकते हैं: अनुक्रम से ओक को हटा दें यदि:
  
  
  • या यह दोनों पड़ोसियों की तुलना में कड़ाई से छोटा है
  • या कड़ाई से उनमें से अधिक
  
  
  उदाहरण के लिए, निम्नलिखित आकृति में, "ओक" को हरे रंग में हाइलाइट किया गया है, जिसे हटाया जा सकता है:

• अनुक्रम को गैर - कड़ाई से बढ़ाना आवश्यक है ताकि कम से कम संचालन के लिए अनुक्रम बढ़ सके। विलोपन अनुक्रम भी घटाया जाना चाहिए। उदाहरण के लिए, इस तरह:

यदि आप चाहें, तो आप इसके बारे में सोच सकते हैं (पद का नाम आपको बता सकता है)।

मुख्य विचार

जैसा कि आप टैग से अनुमान लगा सकते हैं - समाधान एक निश्चित गतिशील है। यदि आप भूल गए या नहीं जानते कि गतिशील प्रोग्रामिंग क्या है, तो मैं आपको याद दिलाऊंगा। गतिकी का विचार यह है कि बहुत छोटे उदाहरणों के लिए (उदाहरण के लिए, एक पेड़) उत्तर स्पष्ट है (कुछ भी नहीं देखा), लेकिन बड़े लोगों के लिए आप एक समाधान प्राप्त कर सकते हैं यदि आप कुछ छोटे स्वतंत्र उप-प्रकारों के समाधान जानते हैं। इस बिंदु पर, गतिशीलता प्रेरण की बहुत याद दिलाती है। समस्या को कैसे कम करें, उदाहरण के लिए, दस पेड़ों को छोटे लोगों के लिए? मान लीजिए कि हम पहले से ही उत्तर जानते हैं (हम इसका उपयोग नहीं करेंगे, लेकिन यह कल्पना करना उपयोगी है)। इसमें दो चरम पेड़ और कुछ बीच हैं। आइए इस मध्य से किसी भी पेड़ पर (सामान्य रूप से, कोई भी पेड़ जो सीमाओं के बीच ऊँचाई पर स्थित हो - अन्यथा आप उसे छोड़ नहीं सकते)



आप देख सकते हैं कि सभी ऑपरेशन बाईं ओर या दाईं ओर किए जाएंगे। इसलिए, वे किसी भी तरह से एक-दूसरे पर निर्भर नहीं होते हैं। इसलिए वे दो स्वतंत्र उप-प्रकारों में विभाजित हो गए। आप हमारे बड़े सेगमेंट पर आराम कर सकते हैं (सबसे अच्छा चुनें) जवाब।

और क्या करना है जब हमारी सीमाओं के बीच अंतराल में पेड़ नहीं हैं (उदाहरण के लिए, पेड़ 4 और 9)? यहां हम समझते हैं कि इस मामले में हमें अंतराल पर सभी पेड़ों को काटने की जरूरत है। सवाल यह है कि किस क्रम में? एक लालची एल्गोरिथ्म बनाने के लिए एक प्रलोभन है: नीचे आने वाले पहले पेड़ को काट दें और जब तक वे बाहर नहीं निकलते हैं। हालांकि, यह गलत है:



मुझे लगता है कि यह स्पष्ट है कि आपको "पिछले दो चरणों में खोज शुरू करें" आदि की शैली में विभिन्न अनुकूलन के साथ नहीं आना चाहिए, - यह सब एक बड़े यादृच्छिक परीक्षण के साथ टूट जाता है।

कुछ ज्यादा ही होशियार चाहिए। हम एक बार पोस्ट के शीर्षक को देखते हैं और उप-खंडों द्वारा बहुत ही समान गतिशीलता के साथ आते हैं: दो पेड़ों और उससे कम के लिए, कुछ भी नष्ट होने की आवश्यकता नहीं है। और अधिक के लिए, आपको पेड़ को छांटने की जरूरत है, जिसे हम अंतिम रूप से हटा देंगे और ध्यान देंगे कि फिर से हमें दो उपप्रकार मिले हैं: बाएं और दाएं। एकमात्र विशिष्ट बिंदु यह है कि आपको यह जांचने की आवश्यकता है कि इस पेड़ को अंत में हटाया जा सकता है (जब अंतराल की सीमाएं अपने पड़ोसियों से मिलती हैं)



उदाहरण के लिए, वृक्ष 4 को अंतिम रूप से हटाया जा सकता है, लेकिन वृक्ष 3 नहीं हो सकता।

उत्तर वसूली

उत्तर को शास्त्रीय विधि द्वारा बहाल किया जाता है - हम सरणी से प्रत्येक राज्य (जहां सबसे अच्छा जवाब पहुंचा था) से इष्टतम संक्रमण को याद करते हैं, और फिर हम अंत से चले जाते हैं। रिकवरी द्वारा उप-खंडों द्वारा डायनामिक्स में रिकवरी लिखना सुविधाजनक है:

उत्तर वसूली

vector < int > ans ; //

// a b - ,

void deleteAll ( int a, int b ) {

assert ( del [ a ] [ b ] >= 0 ) ;

if ( del [ a ] [ b ] == a ) return ;

deleteAll ( a, del [ a ] [ b ] ) ;

deleteAll ( del [ a ] [ b ] , b ) ;

ans. push_back ( del [ a ] [ b ] ) ;

}



//

void restoreAns ( int a, int b ) {

assert ( fr [ a ] [ b ] >= 0 ) ;

if ( fr [ a ] [ b ] == a ) {

deleteAll ( a, b ) ;

return ;

}

restoreAns ( a, fr [ a ] [ b ] ) ;

restoreAns ( fr [ a ] [ b ] , b ) ;

}

काम का समय

कुल में, हमारे पास प्रत्येक गतिकी का O (n ² ) राज्य है (प्रत्येक उप-खंड के लिए एक)। प्रत्येक गतिकी में, संक्रमण O (n) में किया जाता है - अंतराल के अंदर पेड़ पर पुनरावृति। जवाब बहाल करते समय, हम प्रत्येक राज्य में एक बार से अधिक नहीं जाते हैं। यह एक वर्ग के रूप में निकलता है, लेकिन चूंकि यह एक घन से कम asymptotically (असीम रूप से बड़े n पर कम) है, इसलिए इसे उपेक्षित किया जा सकता है।

कुल ऑपरेटिंग समय O (n ³ ) है , जो n = 200 पर O (8 * 10 ⁶ ) है , जो तुरंत काम करता है। यह हमें भी सूट करता है।

कैसे लिखें?

सबसे पहले आपको डेटा को एक ऐरे / वेक्टर में पढ़ना होगा। आप इसे करना जानते हैं।

प्रथम वक्ता

अगला, आपको सभी पेड़ों को हटाने के लिए गतिशीलता की गणना करने की आवश्यकता है। हम इसे सरणी int del [a] [b] - -1 में स्टोर करेंगे यदि अंतराल (a, b) पर सभी पेड़ों को हटाना असंभव है, और अंतिम पेड़ की संख्या अलग है।

उप-खंडों की गणना करने के लिए, यह दो चक्र लिखने के लिए आकर्षक है:

for ( int left = 0 ; left < n ; left ++ )

for ( int right = left ; right < n ; right ++ ) {

// ...

}





हालांकि, यह मौलिक रूप से गलत है, क्योंकि डायनामिक्स का संक्रमण केवल तभी सही होगा जब हम "छोटे" उप-योगों के उत्तर को जानते हैं। हमारे मामले में, छोटी लंबाई के उप-खंडों के लिए। इसलिए, आपको पहले खंड की लंबाई के माध्यम से सॉर्ट करना होगा, और फिर शुरुआत (या अंत):

for ( int l = 2 ; l < n ; l ++ )

for ( int a = 0 ; a + l < n ; a ++ ) {

int b = a + l ;

// ...

}





इस चक्र में, आपको अंतिम पेड़ के माध्यम से सॉर्ट करने और हटाने की संभावना की जांच करने की आवश्यकता है। इसके अलावा, खाली अंतराल के लिए गतिशीलता को आरंभ करना न भूलें:

// h2, h1 h3

bool can ( int h1, int h2, int h3 ) {

if ( h1 < h2 && h3 < h2 ) return true ;

if ( h1 > h2 && h3 > h2 ) return true ;

return false ;

}



// ...

for ( int a = 0 ; a + 1 < n ; a ++ )

del [ a ] [ a + 1 ] = a ;



for ( int l = 2 ; l < n ; l ++ )

for ( int a = 0 ; a + l < n ; a ++ ) {

int b = a + l ;

for ( int i = a + 1 ; i < b ; i ++ )

if ( del [ a ] [ i ] >= 0 && del [ i ] [ b ] >= 0 && can ( h [ a ] , h [ i ] , h [ b ] ) ) {

del [ a ] [ b ] = i ;

break ;

}

}

दूसरा वक्ता

हम दूसरी सरणियों को दो सरणियों में संग्रहीत करेंगे - int dyn [a] [b] और int fr [a] [b] । पहला है, वास्तव में, यदि आप एक गैर-घटते क्रम को नहीं छोड़ सकते हैं, तो सबसिलेशन का उत्तर (कितने न्यूनतम पेड़ों को हटाने की आवश्यकता है), या अनन्तता (मैं 10 ^{9 का} उपयोग करता हूं)। और दूसरे सरणी में हम या तो स्टोर करेंगे -1 यदि अनंत पहले, या आखिरी दूरस्थ पेड़ में लिखा गया है।

इसलिए, हम लिख रहे हैं। यहाँ आप रास्ते में सब कुछ इनिशियलाइज़ कर सकते हैं (एक अलग लूप की आवश्यकता केवल शिशुओं को भरने के लिए है):

//

for ( int l = 1 ; l < n ; l ++ )

for ( int a = 0 ; a + l < n ; a ++ ) {

int b = a + l ;

if ( h [ a ] > h [ b ] ) continue ; // ,

if ( del [ a ] [ b ] >= 0 ) { // ,

dyn [ a ] [ b ] = b - a - 1 ;

fr [ a ] [ b ] = a ;

}



for ( int i = a + 1 ; i < b ; i ++ ) {

// , ,

// -

if ( h [ a ] > h [ i ] || h [ i ] > h [ b ] ) continue ;



// ,

// ,

int cans = dyn [ a ] [ i ] + dyn [ i ] [ b ] ;

if ( dyn [ a ] [ b ] > cans ) {

dyn [ a ] [ b ] = cans ;

fr [ a ] [ b ] = i ;

}

}

}

उत्तर वसूली

यह पहले से ही पूरी तरह से ऊपर लिखा गया है - यह कोड पूरी तरह से काम करता है। यह केवल यह सत्यापित करने के लिए रहता है कि एक उत्तर है, फ़ंक्शन को कॉल करें, और परिणाम का उत्पादन करें:

int a = 0 , b = n - 1 ;

if ( fr [ 0 ] [ n - 1 ] < 0 ) printf ( "-1 \n " ) ;

else {

ans = vector < int > ( ) ;

restoreAns ( a, b ) ;

printf ( "%d \n " , ans. size ( ) ) ;

for ( int i = 0 ; i < ans. size ( ) ; i ++ )

printf ( "%d \n " , ans [ i ] + 1 ) ;

}

सभी एक साथ

पूरे कार्यक्रम को पास्टबिन पर देखा जा सकता है। चूंकि उसने ओलंपिक में लिखा था, स्पीड डायलिंग और कोई टिप्पणी नहीं के लिए कुछ संक्षिप्त विवरण हैं। हालाँकि, मैंने लेख के सभी महत्वपूर्ण कोड का हवाला दिया।

परीक्षण

एल्गोरिथम समस्याओं के परीक्षण के विषय पर, आप कई बड़े लेख लिख सकते हैं। लेकिन हम जल्दी, सही करना चाहते हैं? इसलिए, हमें याद है कि हमने लेख की शुरुआत में परीक्षण कहां से डाउनलोड किया था, उन्हें कहीं अनपैक किया (कार्य को ओक कहा जाता है) और या तो सभी 50 परीक्षण पेन से चलाएं , या check.dpr फ़ाइल ( संकलित ) को संकलित करें और CMD के साथ एक स्क्रिप्ट लिखें:

@echo off

for %% i IN ( tests\ ?? ) DO (

del oaks. in oaks. out > nul 2 >& 1

copy %% i oaks. in > nul 2 >& 1

main > nul 2 >& 1

if errorlevel 1 exit

check oaks. in oaks. out %% i. a

if errorlevel 1 exit

)

echo ALL IS OK !

pause





हम शुरू करते हैं। यदि आपने शिलालेख देखा तो ठीक है! और "कोई भी कुंजी दबाएं" - आपका निर्णय सही है। यदि नहीं, तो एक परीक्षण है जिस पर यह सही ढंग से काम नहीं करता है। इस परीक्षण को देखने के लिए जल्दी मत करो - यह बग को खोजने और ठीक करने के लिए बहुत अधिक उपयोगी होगा।

निष्कर्ष

यही सब मैं बताना चाहता था। मुझे आशा है कि आप सब कुछ समझ गए होंगे और मैंने आपका समय व्यर्थ नहीं किया होगा।

आपका ध्यान के लिए धन्यवाद, आपको स्वीकार करना आसान है।

मुझे रचनात्मक आलोचना करने में खुशी होगी।