Die Frage, die ich hier stellen werde, wurde bereits zuvor in Stack Overflow gestellt. Aber ich bin nicht in der Lage, die Lösungen richtig zu verstehen, die von Skiminok .
Hier ist die Link .
Ich habe die Lösung im obigen Link mit den beiden Beispiel-Testfällen ausprobiert, bin aber nicht in der Lage, die richtige Antwort zu erhalten.
Für den Testfall 1::
N=3 und K=2
5 4 7
Die DAG wird sein::
Anmerkung: Ich habe die obige DAG konstruiert, indem ich sie berücksichtigte:
Seien pi und pj zwei verschiedene Probleme. Dann ziehen wir eine gerichtete Kante von pi zu pj, wenn und nur wenn pj direkt nach pi am selben Tag gelöst werden kann, und zwar fortlaufend. Die folgenden Bedingungen müssen also erfüllt sein:
i < j, denn man sollte die weniger schwierige Aufgabe früher lösen.
|vi - vj| >= K (die Bewertungsanforderung).
Dann habe ich den zweiteiligen Graphen konstruiert unter Berücksichtigung::
Für jede gerichtete Kante (u, v) des ursprünglichen DAG sollte man dem zweiseitigen Graphen eine ungerichtete Kante (au, bv) hinzufügen, wobei {ai} und {bi} zwei Teile der Größe n sind.
Die Antwort =maximale Kardinalitätsübereinstimmung im obigen zweistufigen Graphen.
Übereinstimmung mit maximaler Kardinalität im obigen zweiseitigen Graphen =1 (grün gefärbte Ekde)
Aber die Antwort ist 2.
Ähnlich verhält es sich mit dem Testfall 2:
5 1
5 3 4 5 6
Die MAx-Kardinalität im obigen Diagramm ist MEHR ALS EINS, aber die richtige Antwort ist 1.
Ich glaube, ich implementiere es nicht richtig, bitte können Sie sagen, wo ich Fehler mache oder gibt es eine andere Methode
Gracias.
