====== Shelter ======

‎$n$‎ نفر در مکان‌های ‎$a_2$‎ ، ‎$a_1$‎ تا ‎$a_n$‎ مختصات قرار دارند. می‌خواهیم این ‎$n$‎ نفر را به ‎$m$‎ پناهگاه ببریم طوری که مجموع اندازه‌ای که افراد حرکت می‌کنند کمینه شود و درون هر پناهگاه حداقل یک نفر وجود داشته باشد‎.
‎

می‌دانیم پناهگاه ‎$i$‎ در مکان ‎$b_i$‎ محور مختصات قرار دارد‎.
‎

شما باید برنامه‌ای بنویسید که کم‌ترین میزان حرکت افراد را به دست آورد، طوری که شرایط سؤال برقرار باشد.
‎‎
===== ورودی =====
 
  * در سطر اول ورودی عدد ‎$1 \leq n \leq 4000$‎ آمده است. در سطر بعدی ‎$n$‎ عدد ‎$a_1$‎ تا ‎$a_n$‎ آمده است‎.
  * در سطر سوم ورودی عدد ‎$1 \leq m \leq n$‎ آمده است. در سطر بعدی ‎$m$‎ عدد ‎$b_1$‎ تا ‎$b_m$‎ آمده است‎.  
===== خروجی =====

در تنها سطر خروجی پاسخ سوال را چاپ نمایید.
‎
===== محدودیت‌ها =====


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

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

<WRAP :en>
^  ورودي نمونه  ^  خروجي نمونه  ^
|3 \\ 1 2 3‎ \\ 2 \\ 2 10 | ‎8‎ |

</WRAP>

‎<پاسخ>

ادعا می‌کنیم جواب بهینه‌ای وجود دارد که در آن اگر ‎$m$‎ پناهگاه و ‎$n$‎ آدم را بر حسب مکانشان مرتب کنیم و شماره‌گذاری کنیم، به ازای هر ‎$i$‎ خاصیت زیر برقرار است:
‎‎
  * ‎ بین تمام آدم‌هایی که به ‎$i$‎ پناهگاه اول می‌روند کسی که بیش‌ترین ‎id‎ را دارد در نظر گرفته مثلا ‎$k$‎ می‌گوییم  ‎$i$‎ پناهگاهی خوب است اگر و فقط اگر ‎$k$‎ نفر اول همه به ‎$i$‎ پناهگاه اول رفته باشند.
 پس ادعا می‌کنیم جواب بهینه‌ای وجود دارد که در آن همه‌ی پناهگاه‌ها خوب‌اند. برای اثبات از برهان خلف استفاده کرده. جواب بهینه‌ای را در نظر بگیرید که بیش‌ترین پناهگاه خوب را دارد. اولین پناهگاه غیرخوب را ‎j‎ می‌نامیم و بزرگ‌ترین کسی که به ‎$j$‎ پناهگاه اول رفته را ‎$i$‎ می‌نامیم. بنابراین کسی وجود دارد قبل از ‎$i$‎ مثلا ‎$k$‎ که به پناهگاهی بعد از پناهگاه ‎$j$‎ رفته ‎$k<i$‎ و ‎$match[i] \leq match[j] < match[k ]$‎. ادعا می‌کنیم اگر جفت ‎$i$‎، ‎$k$‎ را با هم عوض کنیم جواب بهتر می‌شود. ‌با انجام این کار (اگر باز پناهگاه ‎$j$‎ خوب نبود با تکرار این عمل) بالأخره به حالتی می‌رسیم که پناهگاه ‎$j$‎ خوب شده و هیچ پناهگاهی بد نشده، بدیهی است که با این تغییر maxID‎ کسانی که به آن رفته اند کم‌تر شده و مسافت مجموع هم بیش‌تر نمی‌شود. و خوبیت باقی پناهگاه ها نیز عوض نمی‌شود‎.
‎
 با توجه به لم بالا می‌توان به صورت پویا (داینامیک)‌ این مسئله را حل کرد. بدین صورت که ‎$DP[i][j]$‎  را برابر با جواب مسئله در صورتی که فقط ‎$i$‎ نفر اول و ‎$j$‎ پناهگاه اول وجود داشته باشند تعریف می‌کنیم. طبق لم بالا بدیهیست که کسانی که به پناهگاه آخر رفته اند می‌تواند ‎$k$‎ آدم آخر باشند‎ $k$)!‎ حداقل یک است). زیرا اگر این ‎$k$‎ تا متوالی از آخر نباشند خوبیت پناهگاه ‎$j-1$‎ از بین می‌رود. کافیست بر روی تعداد افرادی که در پناهگاه ‎$j$‎ ام رفته for‎ زده و اگر هزینه‌ی اینکه ‎$k$‎ نفر آخر در آن رفته باشند را ‎$Cost(k)$‎ بنامیم، در این صورت‎:
‎

‎$DP[i][j] = min_{k=1}^i(DP[i-k][j-1]‎ + ‎Cost(k))$
‎

اما این الگوریتم از ‎$O(n^3)$‎ است که با روش زیر می‌توان آن را به ‎$O(n^2)$‎ کاهش داد.
‎$DPcomplete[i][j]$‎ حداقل هزینه که با ‎$i$‎ انسان اول ‎$j$‎ پناهگاه رو پوشوند که در هر پناهگاه ها حداقل یک نفر باشد و پناهگاه ‎$j$‎ ام خالی است.  و 
‎$DPtemp[i][j]$‎ حداقل هزینه که با ‎$i$‎ انسان اول ‎$j$‎ پناهگاه رو پوشوند که در هر پناهگاه‌ها حداقل یک نفر باشد و پناهگاه ‎$j$‎ ام می‌تواند خالی باشد‎.

‎
‎$DPcomplete[i][j] = DPtemp[i-1][j]‎ + ‎Cost(i‎ -‎> j)$

‎
نفر ‎$i$‎ ام حتما باید به ‎$j$‎ برود حالا باید برای ‎$i-1$‎ نفر که پناهگاه ‎$j$‎ ام می تواند خالی باشد‎!
‎
‎$DPtemp[i][j] = min(DPcomplete[i][j-1]‎ + ‎Cost(i‎ -‎> j-1)‎, ‎DPtemp[i-1][j-1]‎ + ‎Cost(i‎ -‎> j))$

‎
نفر ‎$i$‎ ام می‌تواند به ‎$j$‎ یا ‎$j-1$‎ برود‎.
‎

‎**پيچيدگي**

‎
مرتب کردن اعداد که از ‎$O(n \log n)$است!‎ حافظه داینامیک مورد نیاز هم از ‎$O(n^2)$‎ است و هر خانه آن از ‎$O(1)$‎ بروزرسانی می‌شود. پس پیچدگی کل الگوریتم (هم زمان هم حافظه) ‎$O(n^2)$‎ است‎!‎
</پاسخ>

  * [[سوال ۶۲|سوال بعد]]
  * [[سوال ۶۰|سوال قبل]]