بازی کارت

بازی زیر را در نظر بگیرید. تعدادی کارت وجود دارد که روی هر کدام یک عدد نوشته شده است. یک معامله گر یک توالی از کارت های که روی هر کارت v_iعدد s_i نوشته شده است. سپس دو بازیگر هر کدام یک کارت از توالی را بر می دارند اما فقط میتوانند اولین یا آخرین کارت از باقیمانده کارت ها را بردارند. هدف انتخاب کارت هایی است که بزرگترین مجموع اعداد روی کارت  را داشته باشند. فرض کنید که n زوج است. الگوریتم بهینه ای از مرتبهn² برای بازیگر شماره یک ارائه کنید. با داشتن توالی اولیه, الگوریتم شما باید اطلاعاتی را از قبل با مرتبه درجه دو محاسبه کند و سپس بازیگر شماره یک باید بتواند بطور بهینه انتخاب ها را براساس اطلاعات محاسبه شده در زمان خطی  انجام دهد. 

دریافت
توضیحات: توضیح کد

دریافت
توضیحات: کد