ای سی ام کار تازه وارد

لینک سوال

مفهوم سوال

تو این سوال باید ویترین یک گل فروشی رو طوری بچینیم که بیشترین زیبایی ممکن رو داشته باشه .

ویترین مغازه شامل F طبقه ( سطر ) و هر طبقه شامل V گلدانه .

گلدانها به طبقه چسبیده شدند ! همچنین هر گلدان حداکثر 1 دسته گل رو می تونه تو خودش جا بده .

F تا دسته گل داریم که به ترتیب از 1 , ... , F شماره گذاری شده اند .

سوال از ما می خواد طوری گلهارو بچینیم که گل شماره i سمت سمت چپ گل شماره j باشه . ( i < j )

سوال به ما میزان زیبایی هر گلدان رو میده و ماکزیمم زیبایی ممکن و چینش نهایی رو از ما می خواد .

F , V < 100

حل

برای حل از برنامه ریزی پویا ( DP ) استفاده خواهیم کرد .

فرض کنیم  ( dp( i , j = بهترین حالت ممکن برای قرار دادن i گل در j گلدان اول باشه .

حالا بهترین حالت برای قرار دادن i گل در j گلدان اول

یا گل i ام رو در گلدان j می زاریم پس ماکزیمم زیبایی میشه : ( dp( i-1 , j-1 ) + Cost( i , j

یا تو گلدان j ام چیزی نمی زاریم پس ماکزیمم زیبایی میشه : ( dp( i , j-1

پس

dp( i , j ) = max( dp( i , j-1 ) , dp( i-1 , j-1 ) + Cost( i , j ) )

برای بدست آوردن مسیر هم کافیه زمان بدست آوردن مقدار dp یه مقدار اضافی ( مثلا par ) رو نگه داریم .