Module: الأنماط في البرمجة الديناميكية - 2


Problem

1 /5


ملء اللعبة

Theory Click to read/hide

إخلاء المسؤولية: الطريقة الموضحة أدناه ليست عالمية ، لكنها غالبًا ما تحل مشكلة أو تساعدك في الوصول إلى الحل الصحيح.

إذا طلبت منك مشكلة تدمير / طي / دمج (أو ما شابه) مصفوفة على النحو الأمثل ، فعليك محاولة حلها باستخدام البرمجة الديناميكية على الأجزاء الفرعية.

دعنا نحصل على dp [l] [r] - الإجابة المثلى لشريحة فرعية ذات مؤشرات من l إلى r. تعتمد إعادة حساب الديناميكيات بشكل كبير على المهمة ، ولكن هناك الأفكار العامة التالية:

1) انظر إلى العناصر المتطرفة l و r. إذا كانت تتطابق أو تكمل بطريقة أخرى ، فعلى الأرجح سيكون من الممكن تحديث قيمة dp [l] [r] عبر dp [l + 1] [r-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

يتم إعطاؤك شريطًا من الورق المتقلب مصنوع من n مربعات ملونة مرقمة من 1 إلى n من اليسار إلى اليمين. يتم تلوين المربع i في البداية c i .

نقول أن المربعين i و j يقعان في نفس المكون إذا كان c i & nbsp؛ = c j و c i & nbsp؛ = c k لجميع الأشخاص الذين يرضونهم & lt؛ ك & lt؛ ي. بمعنى آخر ، يجب أن يكون لجميع المربعات في المقطع من i إلى j نفس اللون.
على سبيل المثال ، يحتوي الشريط [3،3،3] على مكون واحد متصل ، بينما يحتوي [5،2،4،4] على 3.

ملء اللعبة لعبت على هذا الشريط على النحو التالي:
في بداية اللعبة ، تختار مربع بدء عشوائي واحد (لا يعتبر هذا بمثابة منعطف).
ثم ، في كل خطوة ، تقوم بتغيير لون المكون المتصل الذي يحتوي على مربع البداية إلى أي لون آخر.

اكتشف الحد الأدنى لعدد الحركات اللازمة لإعادة تلوين الشريط بأكمله بلون واحد.

الإدخال:
يحتوي السطر الأول على عدد صحيح واحد n (1 & le؛ n & le؛ 5000) & [مدش]؛ عدد المربعات

يحتوي السطر الثاني على الأعداد الصحيحة c 1 ، c 2 ، & hellip؛، c n (1 & le؛ c i <5000) و [مدش] ؛ الألوان الأولية للمربعات.

الإخراج:
طباعة عدد صحيح واحد و [مدش] ؛ الحد الأدنى لعدد النقلات التي يجب القيام بها.

أمثلة:
نبسب ؛ <الجسم>
إدخال الإخراج
4
5 2 2 1 		2
8
4 5 2 2 1 3 5 5 		4
1
4 		0

الشرح:
إحدى الطرق المثلى في المثال الأول: [5، 2، 2، 1] - & GT؛ [5 ، 2 ، 2 ، 2] - & GT. [5 ، 5 ، 5 ، 5]

time 2000 ms
memory 256 Mb
Rules for program design and list of errors in automatic problem checking

Teacher commentary

Your Program

Attach a file with the source code of the program:

or select a programming language and type your program

Auto

       

Program check result To check the solution of the problem, you need to register or log in!