المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


سوالات المپیاد:متفرقه:آزمون های اینترنتی ۸۹ تا ۹۱:سوال ۵۳

Intervals

اعداد ‎$a_1$‎ ، ‎$a_2$‎ تا ‎$a_n$‎ به شما داده شده است ، شما باید حداکثر ‎$k$‎ بازه به طول کم‌تر یا مساوی ‎$d$‎ از اعداد را انتخاب کنید به طوری که جمع اعداد درون بازه‌ها بیشینه شود و هر عدد در حداکثر یک بازه باشد‎.‎

ورودی

  • در سطر اول ورودی سه عدد ‎$1 \leq n \leq 1000$‎ ، ‎$1 \leq d \leq n$‎ و ‎$1 \leq k \leq n$‎ آمده است‎.‎
  • در سطر بعدی ‎$n$‎ عدد ‎$a_1$‎ تا ‎$a_n$‎ آمده‌اند‎.‎
  • تمام اعداد ورودی بزرگتر یا مساوی صفراند و جمع اعداد در int‎ جا می شود‎.‎

خروجی

در تنها سطر خروجی جمع اعداد درون بازه‌ها را چاپ نمایید.

محدودیت‌ها

  • محدودیت زمان: ۲ ثانیه
  • محدودیت حافظه: ۲۵۶ مگابایت

ورودی و خروجی نمونه

ورودی نمونه خروجی نمونه
‎5 1 2‎
‎1 5 2 4 3‎
‎9 ‎
5 2 1‎
1 5 2 4 3
‎7‎

پاسخ

با توجه به نوع سؤال، اولین راه‌حلی که به ذهن می‌رسد، استفاده از برنامه‌سازی پویاست، بدین شکل که dp[i][j]‎ را برابر مقدار زیر تعریف کنیم‎:

بیشینه جمع اعداد درون بازه‌ها، به شرطی که اعداد درون بازه‌ها از ‎$i$‎ عدد اول باشند و تعداد بازه‌ها ‎$j$‎ تا باشد.برای به‌دست آوردن مقدار ‎dp[i][j]‎، دو حالت را در نظر می‌گیریم: ‎

  1. عدد ‎$i$‎ ام در هیچ بازه‌ای قرار نداشته باشد: در این صورت، مقدار بهینه برابر ‎dp[i–1][j]‎ می شود.
  2. عدد ‎$i$‎ ام در بازه ی آخر قرار داشته باشد: در این صورت اگر قرار باشد خانه‌ی اول بازه‌ی آخر، عدد ‎$k$‎ام باشد، مقدار بهینه از عبارت زیر بدست می‌آید:

‎$\max_{(i-d \leq k < i)}{dp[k][j-1]‎+ ‎\sum_{t=k+1}^i a_t}$‎

محاسبه‌ی dp[i][j]‎ در حالت اول، از ‎$O(1)$‎ زمان می‌برد، اما در حالت دوم از ‎$O(n)$‎ زمان نیاز دارد. بنابراین کل الگوریتم در زمان ‎$O(n^3)$‎ اجرا می‌شود که با توجه به محدودیت ‎$n < 1001$‎ نیاز به بهبود الگوریتم داریم‎.‎

پیچیدگی زمانی الگوریتم‌های پویا را می‌توان ناشی از دو عامل دانست. اول تعداد وضعیت های موجود و دوم زمانی که صرف محاسبه‌ی مقدار هر وضعیت (که به آن بروزرسانی وضعیت هم می‌گویند) می‌شود. در الگوریتم بالا تعداد وضعیت ها از ‎$O(n^2)$‎ است و بروزرسانی هر وضعیت از ‎$O(n)$‎ انجام می‌شود. بنابراین کل الگوریتم از ‎$O(n^3)$‎ است.

برای بهبود پیچیدگی زمانی الگوریتم باید یکی از این دو عامل را بهتر کنیم. در اینجا ما با بهتر کردن زمان بروزرسانی برای هروضعیت الگوریتم خود را سریع‌تر می‌کنیم‎.

اگر sum[i]‎ را مجموع اعداد اول تا ‎$i$‎ ام دنباله تعریف کنیم، می‌توانیم عبارت بالا را به شکل زیر بازنویسی کنیم:

‎$\max_{i-d \leq k < i}(dp[k][j-1]‎+ ‎\sum_{t=k+1}^i a_t) =$‎

‎$\max_{i-d \leq k < i}(dp[k][j-1]‎+ ‎sum[i]‎- ‎sum[k]) =$‎

‎$sum[i]‎+ ‎\max_{i-d \leq k<i}(dp[k][j-1]‎- ‎sum[k])$‎

بنابراین برای محاسبه‌ی عبارت بالا کافی است، به ازای هر ‎$i$‎ مقادیر مجموعه‌ی $\{dp[k][j-1]‎- ‎sum[k] | i-d \leq k<i \}$‎ را داشته باشیم و مقدار بیشینه‌ی آن را حساب کنیم و سپس با ‎$sum[i]$‎ آن را جمع کنیم. نکته‌ی مهم در این عبارت این است که مجموعه‌ی بالا به ازای ‎$i$‎ های مختلف، بازه‌های متفاوتی برای ‎$k$‎ درنظر می گیرد ولی مقادیر محاسبه شده برای هر ‎$k$‎، یکی می‌باشد. پس اگر ما این مجموعه را برای مقدار ‎$i$‎ حساب کرده باشیم و بخواهیم آن را برای مقدار ‎$i+1$‎ حساب کنیم، کافی است مقدار مربوط به ‎$k = i – d$‎ را از مجموعه حذف کنیم و مقدار مربوط به ‎$k = i$‎ را به مجموعه اضافه کنیم و همین طور برای ‎$i+2$‎ می‌توان مجموعه مطلوب را با حذف کردن یک عنصر و اضافه کردن یک عنصر دیگر به مجموعه ی مربوط به ‎$i+1$‎ بدست آورد. به همین طریق برای هر ‎$i$‎ با حذف کردن و اضافه کردن یک عنصر به مجموعه می توان مجموعه ی مورد نظر را ساخت و با بدست آوردن مقدار بیشینه‌ی این مجموعه مقدار ‎$dp[i][j]$‎ را بروزرسانی کرد. برای انجام بهینه ی این عملیات‌ها، می توان از داده ساختاری مثل Red-Black Tree‎ استفاده کرد که عملیات های حذف و اضافه و ماکسیمم گیری را در ‎$O(\log n)$‎ انجام می‌دهد. بنابراین با احتساب ‎$O(n^2)$‎ وضعیت و ‎$O(\log n)$‎ زمان بروزرسانی، می‌توان زمان الگوریتم پویا رو به ‎$O(n^2 \log n)$‎ بهبود داد.البته با بهتر کردن روش بروز رسانی، می‌توان الگوریتمی از ‎$O(n^2)$‎ ساخت که به عنوان تمرین به خواننده واگذار می شود.


ابزار صفحه