جزیره ای وجود دارد که همه جمعیت آن افراد چشم سبز یا آبی می باشند...
جعبه های مهره و آقوی همساده !-مسئله F ای سی ام دانشگاه فردوسی
شمردن تعداد نا به جایی ها در یک آرایه - کدینگ
سوال کدینگ - dp - فارسی - سوال سخت
سوال 24 مرحله اول المپیاد کامپیوتر دوره 25
سوال 12 مرحله اول دوره 25 المپیاد کامپیوتر
تعداد حالات مکعب روبیک رو حساب کنید.
**4n** توپ داریم **2n**توپ سیاه **2n**توپ سفید
پاسخ سوالات مرحله 2 های دوره های قدیمی
سوال کدیگ:
مربعی n*n در نظر بگیرید ما می خواهیم مسیری را پیدا کنیم که برای رسیدن از بالا سمت چپ و رسیدن به پایین سمت راست بهینه باشد (اگه نفهمیدیید از رو مثال ها متوجه می شید)
ورودی:
به ما n داده می شود سپس سپس مقدار هر خانه را می دهد
خروجی :
مقدار بهینه مسیر حرکت
مثال :
3
5 3 1
6 1 1
7 8 6
خروجی :
16
مثال:
2
1 2
3 2
خروجی:
6
سلام میدونستید انجمن علمی نخبگان دانشگاه صنعتی شریف مسابقه تخصصی مهارت سنجی برنامه نویسی و داده کاوی گذاشته است آدرس سایتش www.fanavard.com
2015-08-06 08:56:03 -0500 امیر شکریسلام میگم یک سر به سایت www.fanavard.ir بزنید. مسابقات برنامه نویسی شون شروع شده. گواهی رسمی از طرف دانشگاه شریف می ده. 50 تا سکه هم جایزشه
2016-10-27 08:05:08 -0500 امیر شکریاین سوال معروفی از مبحث برنامه نویسی پویا است و معمولا تنها به روش های راست یا پایین می توان حرکت کرد (گاهی حرکت اریب هم می توان): اگر بخواهد به مسیر بالا برگردد که بدیهی است minimum مقدار نمی شود! این نکته خیلی واضح است... این از کد دی پی جواب سوال:
یک آرایه دو بعدی جدید به اسم DP گرفته می شود و که خانه سطر i ام و ستون j ام نشان دهنده ی حداقل مقدار برای رسیدن به آن خانه (سطر i ام و ستون j ام) می باشد.بدیهی است مقدار آرایه dp برای سطر اول همیشه برابر جمع خانه های قبلی خود در همان سطر هست. زیرا از راه دیگری نمی توان وارد آن خانه ها شد! برای ستون اول نیز همین قانون وجود دارد. در لینک، ابتدا خانه های سطر اول و ستون اول مقدار دهی شده اند.
برای هر خانه که در سطر اول و ستوان اول نیست، مقدار دی پی می شود مینیموم خانه ی بالایی خود و چپی خود + مقدار همان خانه در ورودی. یعنی حداقل باید همان مقدار ورودی را حساب کرد (به طور مثال داریم پول پرداخت می کنیم!) به علاوه ی بهترین مسیر یافته شده تا آنجا (مینیموم گیری خانه ی بالایی و چپی)
در ضمن جواب خروجی تست کیس دوم گذاشته شده معادل ۵ می باشد که اشتباهاْ ۶ درج شده است.
توضیحات مطابق لینک کد گذاشته شده می باشد. امیدوارم درک کرده باشید. در صورت وجود مغایرت یا ابهام، نظر بگذارید.
نکته جدید: این سوال به صورت بازگشتی نیز می تواند حل گردد (مانند هر سوال dp دیگری)
ممنون كه متن سايت topcoder رو ترجمه كردي D: بعد يك سوال دارم چرا راه حل من اشتباه است و فرق راه حل شما با من چيه ؟؟؟؟؟
2014-08-04 14:05:13 -0500 مبیدیکفكر مي كنم تنها فرقش اينه كه شما تو راه حلت از يك آرايه به نام dp استفاده كردي D:
2014-08-04 14:09:57 -0500 مبیدیکببینید اولا در متن سوال ذکر نشده است که فقط پایین و راست مجاز باشدنوشته [کمترین مسیری بین دوخانه ی مدنظر ] پس بالا و چپ هم مجاز می باشد و دوما اگر اینطور هم بود راه حل مبیدیک درست بود پس به مثال زیر توجه کنید و بیشتر فکر کنید:
5
0 1 0 0 0
0 1 0 1 0
0 1 0 1 0
0 1 0 1 0
0 0 0 1 0
2014-08-04 14:46:16 -0500 طوفان@مبیدیک: بدون آرایه کمکی محال است بتونی به جواب برسی. عصر یک مثال نفض برای کدت می زنم. شما اصلا از دی پی استفاده ای نکردی!!! و اینکه تاپکدر ماکسیمم مقدار رو می خواست نه مینیمم. یک کم فرق داره اولاش. مثل شما کد رو از یه جا کپی پیست نکردم! :دی الان باید بروم مدرسه. عصر بهتون میگم...
2014-08-04 21:06:22 -0500 پاک شدهبهترين الگوريتم براي حل اين سوال يك الگوريتم DP است كه براي هر خانه اي كه درحال حاضر روي آن هستيم خانه ي سمت راست و خانه ي سمت پايين را در نظر بگيريم و هر كدام كه كمتر بود را انتخاب كنيم
( ( path=path+min(Right,Down) .
كد .
