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[ دوباره محاسبه کنیم. k+1][r]. در زیرمجموعه های کوچکتر نیز این بخش ها مرتب شده اند، بنابراین در واقع گزینه های تقسیم زیربخش [l;r] نه تنها به دو قسمت، بلکه به هر تعداد از آنها در نظر گرفته می شود.
 

Problem

یک نوار کاغذ شطرنجی به شما داده می شود که از n مربع رنگی با شماره 1 تا n از چپ به راست ساخته شده است. مربع i در ابتدا به رنگ ci است.

اگر ci = cj و ci = ck می گوییم مربع i و j در یک جزء قرار می گیرند. برای همه k راضی کننده i < k < j به عبارت دیگر، تمام مربع های قسمت i تا j باید یک رنگ باشند.
برای مثال، نوار [3،3،3] دارای 1 جزء متصل است، در حالی که [5،2،4،4] دارای 3 است.

بازی را پر کنید در این نوار به صورت زیر پخش می شود:
در ابتدای بازی، شما یک مربع شروع تصادفی را انتخاب می کنید (این به عنوان یک نوبت به حساب نمی آید).
سپس، در هر حرکت، رنگ جزء متصل حاوی مربع شروع را به هر رنگ دیگری تغییر می دهید.

حداقل تعداد حرکات مورد نیاز برای رنگ آمیزی مجدد کل نوار در یک رنگ را بیابید.

ورودی:
خط اول شامل یک عدد صحیح n (1 ≤ n ≤ 5000) — تعداد مربع ها.

خط دوم شامل اعداد صحیح c1,c2,…,cn (1 ≤ ci <5000) — رنگ های اولیه مربع ها.

خروجی:
چاپ یک عدد صحیح — حداقل تعداد حرکات برای انجام.

مثال:
  <بدن>
ورودی خروجی
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]

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!