====== 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‎ جا می شود‎.‎
 ===== خروجی =====

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

===== محدودیت‌ها =====


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

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

<WRAP :en>
^  ورودی نمونه  ^  خروجی نمونه  ^
|‎5 1 2‎ \\ ‎1 5 2 4 3‎ |‎9 ‎|
|5 2 1‎ \\ 1 5 2 4 3 |‎7‎ |

</WRAP>

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

بیشینه جمع اعداد درون بازه‌ها، به شرطی که اعداد درون بازه‌ها از ‎$i$‎ عدد اول باشند و تعداد بازه‌ها ‎$j$‎ تا باشد.برای به‌دست آوردن مقدار ‎dp[i][j]‎، دو حالت را در نظر می‌گیریم:
‎
  -  عدد ‎$i$‎ ام در هیچ بازه‌ای قرار نداشته باشد: در این صورت، مقدار بهینه برابر ‎dp[i–1][j]‎ می شود.
  -  عدد ‎$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)$‎ ساخت که به عنوان تمرین به خواننده واگذار می شود.

</پاسخ>

  * [[سوال ۵۴|سوال بعد]]
  * [[سوال ۵۲|سوال قبل]]