Module: Muster in der dynamischen Programmierung - 2


Problem

4 /5


Theory Click to read/hide

Diskleimer: Das nachfolgend beschriebene Verfahren ist nicht universell, kann aber oft die Herausforderung erfüllen oder die richtige Lösung erreichen.

Wenn Sie die Existenz eines Resets überprüfen oder eine Reihe von geeigneten Umkehrungen oder etwas finden müssen, sollten Sie über die Anwendung der dynamischen Programmierung für Multiplikatoren nachdenken.

Der Hauptparameter wird die Kampfmaske sein, die zeigt, welche Elemente bereits in der Konversion enthalten sind und welche nicht. Oft ist auch ein zweiter Parameter erforderlich, der zeigt, was das letzte Element war.

Häufige Reklamation ist im Kontext von Graphen zu erkennen. Wir werden daher ein klassisches Beispiel, eine Gambilleton-Straße betrachten.
Hamiltons' Reise ist ein einfacher Weg durch jede Reihe der Zählung einmal. Es kann sich nur als Umwandlung der Länge n vorstellen, wobei n die Anzahl der Spitzen ist. Die Reihenfolge innerhalb dieses Rücksetzens gibt an, wie die Gipfel passieren.

Um die Existenz einer Hamilton-Straße in der Box zu überprüfen, werden wir dp[mask][last] - gibt es einen einfachen Weg, der die in der Fledermausmaske markierten Spitzen bestanden hat und am oberen Ende endete.
Anfangswerte werden dp[2I][i] = wahr, der Rest ist falsch, was bedeutet, dass es immer einen leeren Pfad gibt, der an einem der Oberseiten beginnt.
Mit der Bedeutung von wahr in dp[mask][letzte] werden wir die Übergänge nach vorne im Sinne von "verkaufter Straße" machen. Wir suchen also nach der Anzahl der Spitzen, die in der Maske vernichtet werden (wir haben sie nicht im Weg besucht) und dass es eine Rippe von letzter bis zu dieser Spitze gibt (die Menge muss durch die vorhandene Rippe erweitert werden). Wir tun dp[mask есть 2k.][k] = wahr, wenn dp[mask][last] = true und mask 2k. = 0 (über k noch nicht besucht) Und es gibt eine Rippen-Letzt-national k.
Letztlich sind Hamiltons auf dem Weg, wenn es einen Wert in dp auf die Parameter einer Kampfmaske gibt, die nur aus Einheiten und jedem letzten Peak besteht.

Problem

Einmal war Mr. Quark in den Händen einer Schatzkarte. Die Karte zeigt N Punkte, an denen sich die Speicherung befinden kann. Alle Punkte werden zwischen 1 und N numeriert. Für jedes Paar Punkte weiß Quark die Länge der Straße, die sie verbindet. Quarks Suche beginnt von Punkt 1. Bevor er sich auf seine lange Reise begibt, schneidet der clevere Zwerg die Punkte heraus, an denen er glaubt, dass der Schatz nicht gebaut werden kann. Es ist gewährleistet, dass der Punkt mit Nummer 1 nie gelöscht wird. Quark wählt dann einen Weg durch alle übrigen Punkte auf der Karte. Marshrut geht nicht mehr als einmal durch denselben Punkt. Quark kann nur auf Straßen gehen, die ungeschnittene Punkte verbinden.

Quark will eine Mindestlängenstrecke wählen. Wir müssen eine solche Route für Quark finden.

Eingangsdaten
Die erste Zeile enthält eine ganze Anzahl von N (1 ≤ N ≤ 15), die Anzahl der auf der Karte markierten Punkte. In nachfolgenden N-Leitungen befinden sich die Abstände zwischen Punkten. In (i+1) ist die Linie N der ganzen Zahlen d1,dINSGESAMT, dN - Längen von i-point zu allen anderen. Garantierte dij= dIji, dii0 und 0 PERdij pé100. In der (N+2) Linie gibt es eine ganze Anzahl von Q (1 Q ≤ 1000), die Anzahl der Optionen zur Entfernung von Punkten für die Karte. Nachfolgende Q-Zeilen beschreiben die Ausrückoptionen. Die Beschreibung beginnt mit der Nummer C (0 < C RE N) - die Anzahl der Punkte, an denen Quark hält, dass das Gehalt nicht bereitgestellt werden kann. Die nächsten C-Nummern fragen die Zahlen dieser Punkte.

Ausgangsdaten
Holen Sie Q gerade. In jeder Zeile, entfernen Sie eine ganze Zahl, die Länge der minimalen Route, mit der entsprechenden Cut-off-Option.
Beispiele
NeinEingangsdatenAusgangsdaten
13
0 45 10
45 0 30
10 30 0
2
0)
1 3		40
45.
25.
0 14 20 17 14
14 0 15 19 18
20 15 0 15 16
17 19 15 0 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!