Module: الگوها در برنامه نویسی پویا - 2


Problem

4 /5


آدم کوتوله

Theory Click to read/hide

سلب مسئولیت: روشی که در زیر توضیح داده شده است جهانی نیست، اما اغلب می تواند یک مشکل را حل کند یا به شما کمک کند تا راه حل مناسب را پیدا کنید.

اگر باید وجود جایگشت را در یک مشکل بررسی کنید، یا تعداد جایگشت‌های منطبق یا چیزی مشابه را بیابید، باید از برنامه‌نویسی زیرمجموعه پویا استفاده کنید.

پارامتر اصلی یک بیت ماسک خواهد بود که نشان می‌دهد کدام عناصر قبلاً در جایگشت گنجانده شده‌اند و کدام‌ها نیستند. همچنین اغلب مورد نیاز یک پارامتر دوم است که نشان می دهد کدام عنصر در آخرین بار گنجانده شده است.

اغلب جایگشت ها را می توان در زمینه مسیرها در نمودارها مشاهده کرد. بر این اساس، اجازه دهید یک مثال کلاسیک را در نظر بگیریم - مسئله مسیر همیلتونی.
مسیر همیلتونی یک مسیر ساده است که دقیقاً یک بار از هر رأس نمودار می گذرد. می توان آن را به سادگی به عنوان یک جایگشت طول n نشان داد، که در آن n تعداد رئوس است. ترتیب درون این جایگشت نشان دهنده ترتیب پیمودن رئوس در این مسیر است.

برای بررسی وجود یک مسیر همیلتونی در نمودار، اجازه دهید دینامیک dp[mask][last] را شروع کنیم - آیا مسیر ساده ای وجود دارد که رئوس علامت گذاری شده در بیت ماسک را دور زده و به آخرین راس ختم شود.
مقادیر اولیه dp[2i][i] = true و بقیه false خواهد بود، به این معنی که همیشه یک مسیر خالی وجود دارد که از هر یک از رئوس شروع می شود.
با داشتن مقدار true در dp[mask][last]، به معنای "توسعه مسیر" به جلو حرکت خواهیم کرد. یعنی به دنبال اعداد رئوس هایی می گردیم که در ماسک با صفر مشخص شده اند (هنوز در راه از آنها بازدید نکرده ایم) و در عین حال به گونه ای هستند که یک یال از آخرین تا این راس وجود داشته باشد (مسیر باید توسط یک لبه موجود گسترش یابد). یعنی dp[mask | را انجام می دهیم 2k][k] = درست اگر dp[mask][last] = true AND mask & 2k = 0 (راس k هنوز بازدید نشده است) و آخرین لبه وجود دارد -> k.
در نهایت، اگر یک مقدار واقعی در dp برای پارامترهای بیت ماسک همه یک‌ها و هر رأس آخر وجود داشته باشد، یک مسیر همیلتونی وجود دارد.

Problem

یک بار کوارک کوتوله با نقشه گنج روبرو شد. بر روی نقشه N نقطه مشخص شده است که گنج را می توان یافت. همه نقاط از 1 تا N شماره گذاری شده اند. برای هر جفت نقطه، کوارک طول جاده ای را که آنها را به هم وصل می کند می داند. کوارک جستجوی خود را از نقطه شماره 1 آغاز می کند. کوتوله حیله گر قبل از شروع سفر طولانی خود، از نقاطی عبور می کند که به نظر او گنجی وجود ندارد. تضمین می شود که نقطه شماره 1 هرگز خط زده نشود. پس از آن، کوارک مسیری را انتخاب می کند که از تمام نقاط باقی مانده روی نقشه می گذرد. مسیر بیش از یک بار از یک نقطه عبور نمی کند. کوارک فقط می تواند در جاده هایی راه برود که نقاط متقاطع را به هم متصل می کنند.

کوارک می خواهد مسیری با حداقل طول انتخاب کند. یافتن چنین مسیری برای کوارک ضروری است.

ورودی
خط اول شامل یک عدد صحیح N (1 ≤ N ≤ 15) — تعداد نقاط مشخص شده روی نقشه N خطوط بعدی شامل فواصل بین نقاط است. خط (i+1)-امین N عدد صحیح di1,di2, diN — طول جاده ها از نقطه i ام تا تمام جاده های دیگر. تضمین شده است که dij=dji، dii=0 و 0 <dij < 100 . خط (N+2)ام شامل یک عدد صحیح Q (1 < Q ≤ 1000) — تعداد گزینه های حذف نقاط برای این نقشه. خطوط Q زیر حاوی توضیحاتی در مورد گزینه های حذف هستند. توضیحات با عدد C (0 ≤ C < N) — تعداد نقاطی که به گفته کوارک گنج نمی تواند باشد. اعداد C بعدی اعداد این نقاط را نشان می دهند.

حصر
خطوط Q را چاپ کنید. در هر خط یک عدد صحیح — طول حداقل مسیر با گزینه مربوط به حذف نقاط.
نمونه‌ها
<سر> <بدن>
# ورودی خروجی
1 3
0  45 10
45 0  30
10 30 0
2
0
1 3 		40
45
2 5
0  14 20 17 14
14 0  15 19 18
20 15 0  15 16
17 19 15 0  14
14 18 16 14 0
2
3 5 4 3
0		 14
58

time 1000 ms
memory 256 Mb
Rules for program design and list of errors in automatic problem checking

Teacher commentary

Your Program

Attach a file with the source code of the program:

or select a programming language and type your program

Auto

       

Program check result To check the solution of the problem, you need to register or log in!