n خان رستم

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

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

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

راه حل

در ادامه راه حلی از این سوال رو با استفاده از برنامه‌نویسی پویا (داینامیک) توضیح می‌دم. مقدار dp[i][c] رو برابر با بیشترین قدرت ممکن همدست‌های رستم در نظر بگیرید در صورتی که می‌تونه i تا اژدهای اول رو با خرج کردن حداکثر c تومن پول، پشت سر بذاره. در غیر این صورت مقدار dp[i][c] برابر با -۱ خواهد بود. برای به دست آوردن مقدار dp[i][c] باید دو تا حالت رو در نظر بگیریم. حالت اول وقتی هست که به اژدهای i رشوه نداده باشیم و با اون جنگیده باشیم. شرط وجود داشتن چنین حالتی اینه که p_i ≤ dp[i-۱][c]. زیرا باید حداقل قدرت برای شکست دادن اژدهای i ام رو تا قبل از این کسب کرده باشیم. حالت بعدی هم وقتی هست که به اژدهای i‌ رشوه بدیم و همدستمون بشه. شرط وجود داشتن این حالت اینه که dp[i-۱][c-c_i] برابر با -۱ نباشه. در حالت اول بیشینه‌ی قدرت همدست‌های رستم برابر با dp[i-۱][c] هست و در حالت دوم این مقدار برابر با dp[i-۱][c-c_i]+p_i است و در صورتی که هیچ کدام از این دو حالت قابل دسترسی نباشند -۱ می‌شود.

در انتها باید کمترین x رو پیدا کنیم که dp[n][x] برابر با -۱ نباشه.

توضیحات

توضیح خاصی که نیست. این سوال مال کانتست اخیر Topcoder‌ بود و بر خلاف اکثر شرکت کننده‌ها که سوال رو خیلی سریع حل کردن شرکت کننده‌های ایرانی (از جمله خودم) تقریبن همه‌شون توی این سوال به کندی عمل کردن و امتیاز‌های خیلی پایینی کسب کردن. طبق چیزایی که می‌دونم ضعف ایرانی‌ها تو این سوال و احتمالن سوال‌های مشابهش ریشه در نوع تغذیه‌ی افراد در این منطقه و آب و هوای ایران نداره. به هر حال هنوز دلیلی واسه این عملکرد ضعیف نمی‌بینم!

توضیحات بیشتر

راه حلی که اول کار به ذهن همه می‌رسه اینه که dp[i][p] رو برابر با کمترین هزینه لازم بگیریم طوری که i‌ اژدهای اول رو پشت سر بذاریم و قدرت همدستامون p باشه. ولی چنین state‌هایی برای داینامیکمون نمی‌تونیم بگیریم چون محدودیتی بر روی قدرت اژدها‌ها نیست. ایده‌ای که توی چند تا سوال تا حالا دیدم اینه که وقتی داینامیکی داریم که یکی از پارامتر‌هاش حالت‌های زیادی داره ولی جوابش حالت‌های کمی داره در عوض می‌شه بعضی وقت‌ها بیشینه یا کمینه‌ی اون پارامتر رو برای هر جواب خاص به دست بیاریم. یا به عبارتی جای پارامتر و جواب رو توی داینامیکمون عوض کنیم تا تعداد state‌ها کمتر بشه. دو تا سوال که الآن توی ذهنم هستن و از این ایده می‌شه روشون زد اینا اند:

• Phone Talks -- http://codeforces.com/contest/158/problem/E
• Brand New Problem -- http://codeforces.com/contest/201/problem/D