طراحی الگوریتم برای مدیریت مسافرت(برنامه نویسی پویا)

---

شرح پروژه

مدیریت مسافرت-برنامه نویسی پویا

میخواهیم طبق مسئله‌ی زیر بین شهر‌ها مسافرت کنیم،مسافرت شما از شهر الف شروع میشود و با رسیدن به شهر ب خاتمه مییابد. از آنجایی که شما نمیتوانید کل مسیر را یک دفعه طی کنید، باید در بین راه استراحت داشته باشید. فرض کنید که تعداد n شهر در مسیر بین شهر الف تا شهر ب وجود دارد که در هر شهر نیز یک هتل خوب برای اقامت وجود دارد. میدانیم که شهر i ام در فاصله m_imi​ کیلومتری از شهر مبدا یا همان شهر الف قرار دارد و

0<m_1<m_2<m_3<...<m_n0<m1​<m2​<m3​<...<mn​

و شهر مبدا در مکان صفر قرار دارد و شهر n ام همان شهر مقصد (شهر ب) است. برای سادگی، هزینه اقامت در همه هتلها را با هم یکسان در نظر بگیرید و فرض کنید که هزینه یک شب اقامت در هتل برابر با عدد k است که در فایل ورودی به شما داده میشود.

برای انجام این مسافرت به صورت زمینی، شما باید چند قانون را رعایت کنید:

برای جلوگیری از خستگی مفرط در رانندگی!، در طول یک روز نباید بیش T کیلومتر را طی کنید. در صورتی که کمی بیشتر از این مقدار و یا کمتر از این مقدار رانندگی کنید (مثلا x کیلومتر رانندگی کنید)، میزان هزینه شما برابر با (T-x)^{2}(T−x)2 خواهد بود.

در پایان روز باید حتما در یکی از شهرهای میانی استراحت کنید و نمیتوانید در میانه راه و خارج از شهر چادر بزنید و شب را به صبح برسانید.

با استفاده از برنامه نویسی پویا، روشی را طراحی و پیاده سازی کنید که شهرهای میانی برای اقامت را به گونه ای انتخاب کند که مجموع هزینه شما (هزینه های ناشی رانندگی کمتر یا بیشتر از T کیلومتر + هزینه های اقامت در هتل ) در سفر حداقل باشد.

ورودی

فایل info.txt است که در خط اول آن عدد n یا تعداد شهرهای میانی، در خط دوم آن عدد k یا هزینه یک شب اقامت در هتل، در خط سوم T یا میزان مجاز رانندگی در روز و در خطوط بعدی به ترتیب فاصله شهرهای میانی تا شهر مبدا ذکر شده است.

خروجی

فایل cost.txt است که در آن در خط اول مجموع هزینه سفر و در خطهای بعدی آن به ترتیب شهرهای میانی که برای اقامت انتخاب شده اند نوشته میشود. توجه داشته باشید که شهر آخر همان شهر مقصد است.

#مثال

ورودی نمونه

3 50 300 290 300 580

Copy

خروجی نمونه

300 1 3

مهارت ها و تخصص های مورد نیاز

---

---