Ich habe dieses Problem irgendwo in einem Wettbewerb gefunden und konnte noch keine Lösung finden.
Ich habe die positiven ganzen Zahlen. Ich muss die längste Untermenge finden, die unter Je zwei Nachbarelemente trennt man ein anderes.
Was ich mache ist: Ich erstelle den Graphen. Dann verbinde ich Knoten, in denen Zahlen sich gegenseitig teilen. Danach verwende ich DFS (ein Knoten kann mit zwei Knoten verbunden sein).
Aber nicht alle Testfälle sind im System wahr. Muss ich das Array vor der Verwendung von DFS sortieren? Vielleicht gibt es einen speziellen (dynamischen) Algorithmus?
Fehlgeschlagene Testfälle:
%Vor% Mein Code gibt die Ausgabe 4 . Aber wenn ich arrange dieses Array so:
Die Ausgabe ist 5 und es ist die wahre Antwort.
Ich habe auch rekursive Methode verwendet. Aber ich brauche etwas schneller.
Dies ist der längste Weg, leicht getarnt. Wir können dieses Problem als längsten Pfad lösen, indem wir einen Graphen erstellen, in dem zwei Vertices genau dann benachbart sind, wenn sie eine Teilbarkeitsbeziehung erfüllen. Siehe unten die horizontale Regel für einen Zeiger auf die beabsichtigte Antwort.
Die Reduktion ist (grob gesagt) bei einem ungerichteten Graphen, in dem wir den längsten einfachen Pfad finden möchten, jedem Knoten eine eigene Primzahl zuweisen. Senden Sie diese Primzahlen zusammen mit, für jede Kante, den Semiprime, der das Produkt seiner Endpunkte ist. (Wir brauchen auch zwei weitere Primzahlen und ihre 2 | V | -Produkte mit den Eckpunkten, um das Ziel additiv zu erhalten.)
Zum Beispiel, wenn wir ein Diagramm haben
%Vor%Dann können wir
beschriften %Vor%und dann ist die Eingabe
%Vor% und (z. B.) der längste Pfad 2, 3, 5, 7 entspricht der längsten Sequenz 11*2, 2, 2*3, 3, 3*5, 5, 5*7, 7, 7*13 (und drei weiteren Varianten mit Umkehrung und Austausch 11 und 13 ).
Der längste Pfad ist NP-schwer, also ist nhahtdhs Kommentar über ein O (2 ^ n poly (n)) - Zeitdynamikprogramm direkt am Geld - siehe diese Frage und die akzeptierte Antwort: Längster Pfad im ungewichteten ungerichteten Graphen .
Sie vergessen, einige Variablen zu reintegrieren: used und kol .
Außerdem stellt DFS used[i] am Ende für die nächsten Aufrufe nicht wieder her.
Versuchen Sie, globale Variablen zu vermeiden, es macht den Code weniger klar. Versuchen Sie auch, den Umfang der Variablen zu reduzieren.
Der Code sieht möglicherweise so aus:
%Vor%und in main:
%Vor% Der Code könnte noch mehr vereinfacht werden (verwenden Sie vector , ...)
Tags und Links algorithm c++ graph-theory depth-first-search