खेल भरें
अस्वीकरण: नीचे वर्णित विधि सार्वभौमिक नहीं है, लेकिन यह अक्सर समस्या का समाधान कर सकती है या आपको सही समाधान तक पहुंचने में मदद कर सकती है।
यदि कोई समस्या आपको किसी सरणी को इष्टतम रूप से नष्ट/संक्षिप्त/मर्ज (या समान) करने के लिए कहती है, तो आपको उपखंडों पर गतिशील प्रोग्रामिंग का उपयोग करके इसे हल करने का प्रयास करना चाहिए।
आइए dp[l][r] - l से r तक के सूचकांकों वाले उपखंड के लिए इष्टतम उत्तर प्राप्त करें। डायनामिक्स की पुनर्गणना अत्यधिक कार्य पर निर्भर है, लेकिन निम्नलिखित सामान्य विचार हैं:
1) चरम तत्वों l और r को देखें। यदि वे किसी अन्य तरीके से मेल खाते हैं या पूरक हैं, तो सबसे अधिक संभावना है कि डीपी [एल] [आर] के मूल्य को डीपी [एल + 1] [आर-1] के माध्यम से अपडेट करना संभव होगा। अन्यथा dp[l][r-1] या dp[l+1[r].
द्वारा
2) अक्सर ऐसा होता है कि खंड [l;r] को एक निर्माण के माध्यम से प्रदर्शित नहीं किया जा सकता है। फिर इस उपखंड के सभी संभावित वर्गों को दो भागों में विचार करना आवश्यक है, अर्थात, तत्व k पर l से r-1 तक पुनरावृति करें और dp [l] [r] के माध्यम से dp [l] [k] और dp [ की पुनर्गणना करें। के + 1] [आर]। छोटे उपखंडों में, इन वर्गों को भी हल किया गया था, इसलिए, उपखंड [l;r] को न केवल दो भागों में विभाजित करने के विकल्प, बल्कि उनमें से किसी भी संख्या को ध्यान में रखा जाता है।
Problem
आपको बाएँ से दाएँ 1 से n तक संख्यांकित n रंगीन वर्गों से बने चेकर पेपर की एक पट्टी दी जाती है। i-वें वर्ग को शुरू में ci से रंगा गया है।
हम कहते हैं कि वर्ग i और j एक ही घटक में स्थित हैं यदि ci = cj और ci = ck सभी k संतोषजनक i < कश्मीर < जे। दूसरे शब्दों में, i से j तक के सेगमेंट के सभी वर्गों का रंग एक जैसा होना चाहिए।
उदाहरण के लिए, स्ट्रिप [3,3,3] में 1 जुड़ा हुआ घटक है, जबकि [5,2,4,4] में 3 है।
खेल भरें इस स्ट्रिप पर इस प्रकार खेला जाता है:
गेम की शुरुआत में, आप एक यादृच्छिक प्रारंभिक वर्ग चुनते हैं (इसे एक मोड़ के रूप में नहीं गिना जाता है)।
फिर, प्रत्येक चाल पर, आप प्रारंभिक वर्ग वाले कनेक्टेड घटक का रंग किसी अन्य रंग में बदलते हैं।
पूरी पट्टी को एक रंग में फिर से रंगने के लिए आवश्यक चालों की न्यूनतम संख्या ज्ञात करें।
इनपुट:
पहली पंक्ति में एक पूर्णांक n (1 ≤ n ≤ 5000) — वर्गों की संख्या।
दूसरी पंक्ति में पूर्णांक हैं c1,c2,…,cn (1 ≤ ci <5000) — वर्गों के प्रारंभिक रंग।
आउटपुट:
एक पूर्णांक प्रिंट करें — चलने की कम से कम संख्या।
उदाहरण:
<तालिका सीमा = "1" सेलपैडिंग = "1" सेलस्पेसिंग = "1" शैली = "चौड़ाई: 500 पीएक्स;">
<शरीर>
| इनपुट |
आउटपुट |
4
5 2 2 1
| 2 |
8
4 5 2 2 1 3 5 5
| 4 |
1
4
| 0 |
व्याख्या:
पहले उदाहरण में इष्टतम तरीकों में से एक: [5, 2, 2, 1] -> [5, 2, 2, 2] -> [5, 5, 5, 5]