Module: الأنماط في البرمجة الديناميكية - 2


Problem

4 /5


قزم

Theory Click to read/hide

إخلاء المسؤولية: الطريقة الموضحة أدناه ليست عالمية ، لكنها غالبًا ما تحل مشكلة أو تساعدك في الوصول إلى الحل الصحيح.

إذا كنت بحاجة إلى التحقق من وجود تبديل في مشكلة ، أو العثور على عدد التباديل المطابق ، أو شيء مشابه ، فعليك إذن التفكير في استخدام برمجة مجموعة فرعية ديناميكية.

ستكون المعلمة الرئيسية عبارة عن قناع بت ، والذي سيُظهر العناصر التي تم تضمينها بالفعل في التقليب ، والتي لم يتم تضمينها. غالبًا ما يكون مطلوبًا أيضًا معلمة ثانية تشير إلى العنصر الذي تم تضمينه مؤخرًا.

غالبًا ما يمكن رؤية التباديل في سياق المسارات في الرسوم البيانية. وبناءً على ذلك ، دعونا ننظر في مثال كلاسيكي - مشكلة مسار هاميلتوني.
مسار هاميلتوني هو مسار بسيط يمر عبر كل رأس من الرسم البياني مرة واحدة بالضبط. يمكن تمثيله ببساطة على أنه تبديل للطول n ، حيث n هو عدد الرؤوس. سيشير الترتيب ضمن هذا التبديل إلى الترتيب الذي يتم فيه اجتياز الرؤوس في هذا المسار.

من أجل التحقق من وجود مسار هاميلتوني في الرسم البياني ، فلنبدأ ديناميكيات dp [القناع] [الأخير] - هل هناك مسار بسيط تجاوز الرؤوس المميزة بأخرى في القناع النقطي للقناع وانتهى به الأمر عند القمة الأخيرة.
ستكون القيم الأولية هي dp [2 i ] [i] = صحيح ، والباقي خطأ ، مما يعني أن هناك دائمًا مسارًا فارغًا يبدأ من أي من القمم.
بالحصول على القيمة صحيحة في dp [القناع] [الأخير] ، سنقوم بإجراء انتقالات للأمام ، بمعنى "توسيع المسار". وهذا يعني أننا سنبحث عن عدد القمم التي تم تمييزها بصفر في القناع (لم نقم بزيارتها بعد في الطريق) وفي نفس الوقت توجد حافة من الأخير إلى هذا الرأس (يجب أن يكون المسار يتم تمديده بواسطة حافة موجودة). وهذا يعني أننا نقوم بعمل dp [mask | 2 k ] [k] = true if dp [mask] [last] = true AND Mask & amp؛ 2 k = 0 (لم تتم زيارة الرأس k بعد) وهناك حافة أخيرة - & gt؛ ك.
في النهاية ، يوجد مسار هاميلتوني إذا كانت هناك قيمة حقيقية في dp لمعلمات كل قناع البت وأي قمة أخيرة.

Problem

بمجرد أن جاء القزم كوارك عبر خريطة الكنز. هناك نقاط N محددة على الخريطة حيث يمكن العثور على الكنز. جميع النقاط مرقمة من 1 إلى N. لكل زوج من النقاط ، يعرف Quark طول الطريق الذي يربط بينهما. يبدأ كوارك بحثه من النقطة رقم 1. قبل أن يبدأ رحلته الطويلة ، يقوم القزم الماكر بتخطي النقاط التي ، في رأيه ، لا يمكن أن يكون هناك كنز. من المؤكد أن النقطة رقم 1 لا يتم شطبها أبدًا. بعد ذلك ، يختار Quark مسارًا يمر عبر جميع النقاط المتبقية على الخريطة. لا يمر المسار عبر نفس النقطة أكثر من مرة. يمكن للكوارك أن يمشي فقط على الطرق التي تربط بين النقاط غير المتقاطعة.

يريد كوارك اختيار مسار بأدنى طول. من الضروري إيجاد مثل هذا الطريق لكوارك.

إدخال
يحتوي السطر الأول على عدد صحيح واحد N (1 & le؛ N & le؛ 15) & [مدش]؛ عدد النقاط التي تم تحديدها على الخريطة. تحتوي الأسطر N التالية على المسافات بين النقاط. يحتوي السطر (i + 1) -th على N أعداد صحيحة d i1 و d i2 و d iN & mdash؛ أطوال الطرق من النقطة i إلى جميع الطرق الأخرى. مضمون أن d ij = d ji و d ii = 0 و 0 & lt؛ d ij & lt؛ 100. السطر (N + 2) يحتوي على عدد صحيح واحد Q (1 & lt؛ Q & le؛ 1000) & [مدش]؛ عدد خيارات حذف النقاط لهذه الخريطة. تحتوي سطور Q التالية على وصف لخيارات الحذف. يبدأ الوصف بالرقم C (0 & le؛ C & lt؛ 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 & nbsp؛ 15 16
17 19 15 0 & nbsp؛ 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!