n خان رستم

سلام، این سوال رو فعلن داشته باشید، بعدن راه حل و توضیحات رو اضافه می‌کنم. :)

رستم می‌خواد «n-خان رستم» رو پشت سر بذاره تا برای خودش اسطوره‌ای بشه. برای این کار باید به ترتیب خان یکم تا خان n-ام رو پشت سر بذاره. در خان i-ام باید از پس اژدهای i-ام بر بیاد. قدرت اژدهای i رو با p_i نشون می‌دیم. قدرت هر اژدها یه عدد صحیح مثبته. رستم تو خان i می‌تونه به اژدها مقدار c_i تومن رشوه بده و اینطوری اون اژدها همدست رستم می‌شه و دیگه باهاش نمی‌جنگه. اژدها‌ها زیاد دنبال پول نیستن، در نتیجه هر اژدها یا ۱ تومن یا ۲ تومن رشوه می‌خواد. اگه رستم به اژدهای i-ام رشوه نده اون موقع باید با اون اژدها بجنگه. اژدها در صورتی تو مبارزه با رستم و همدستاش پیروز می‌شه که قدرتش از مجموع قدرت اژدها‌های همدست رستم بیشتر باشه. قدرت خود رستم تاثیری تو مبارزه نداره. حالا رستم می‌خواد با کمترین هزینه n-خان رستم رو پشت سر بذاره. الگوریتمی از O(n^۲)  بدید که کمترین هزینه‌ای که رستم باید از جیبش بده رو حساب کنه. واضحه که رستم باید حتمن به اژدهای خان یکم رشوه بده،‌ چون در ابتدا قدرتی نداره.

به روز رسانی: راه حل و توضیحات اضافه شد. (۱۸ دی ۹۱) (۹ دی ۹۱)