spieleprogrammierer.de - Forum und Wiki zur Spieleprogrammierung und Spieleentwicklung

Ich bin jetzt nicht der Fachmann in Sachen dynamische Programmierung.
Bei Wikipedia steht:

Zitat

"Dynamische Programmierung kann dann erfolgreich eingesetzt werden, wenn das Optimierungsproblem aus vielen gleichartigen Teilproblemen besteht, und eine optimale Lösung des Problems sich aus optimalen Lösungen der Teilprobleme zusammensetzt"

Ist dies denn hier der Fall?

Ich denke nicht! Denn wenn ich z.B. die Karte in zwei Hälften teile und jede davon optimal löse, dann kann ich beim Zusammensetzen immer noch durch die Nahtstelle und den damit verbundenen Punktabzug suboptimal werden. Außerdem könnte es sein, dass ich bei einer der beiden Lösungen gezwungenermaßen eine der beiden Zivilisationen benachteilige. Das könnte ich in der anderen Hälfte theoretisch wieder ausgleichen. Löse ich jedoch beide getrennt, weiß ich davon garnichts und kann das nicht berücksichtigen.

An den oben genannten O(n²)-Algorithmus glaube ich jedenfalls nicht.
Zumal da "n" die Anzahl der Zeilen sein soll - und die Anzahl der Spalten ist dann völlig irrelevant, was die Komplexität angeht?

Zitat von »FalkT«

Dürfen wir die Lösung für den Contest in eine Klasse packen und es wird vor Programm-Ausführung ein Objekt dieser Klasse instanziiert ?
Dein benötigtes Interface wäre dann eine statische Member-Funktion.

Du kannst auch einfach eine (lokale, von mir aus auch außerhalb der Funktion befindliche) Klasse definieren und davon dann eine Instanz innerhalb der "dividePlanet" erzeugen und damit machen, was Du willst.