اعداد $a_1$ ، $a_2$ تا $a_n$ به شما داده شده است ، شما باید حداکثر $k$ بازه به طول کمتر یا مساوی $d$ از اعداد را انتخاب کنید به طوری که جمع اعداد درون بازهها بیشینه شود و هر عدد در حداکثر یک بازه باشد.
در تنها سطر خروجی جمع اعداد درون بازهها را چاپ نمایید.
| ورودی نمونه | خروجی نمونه |
|---|---|
| 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]، دو حالت را در نظر میگیریم:
$\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)$ ساخت که به عنوان تمرین به خواننده واگذار میشود.