Ich vermute, dass optimales Ergebnis exponentielle Komplexität hat:
Um die optimale Punktzahl zu erreichen reicht es nicht für jede Vertikale das Optimum zu finden, sondern man muss ja auch die Sache mit den schwach steigenden Linien beachten - das kann auch zu "nicht-intuitiven" Ergebnissen führen, was für das Optimum einen Backtracing-Algorithmus naheliegen lässt. Tjo also muss man x Linien die Score ermitteln: x*Breite*Höhe
Wieviele Möglichkeiten gibt es also für Linien? Nunja also für jede Vertikale hat man soviel Möglichkeiten wie die Vertikalen hoch sind. Für jeden Höhenwert in einer Vertikalen können auch alle anderen anders sein - also Höhe ^ Breite (wie bei einem Zahlenschloss mit Breite Rädern und mit je Höhe Werten)
Alle Möglichkeiten durchgehen wäre also dann O(Breite * Höhe * Höhe ^ Breite) = O(Höhe ^ Breite) also exponentielle Komplexität auf die Breite betrachtet.
Eine Art greedy hab ich übrigens schon ausprobiert - ist eine Katastrophe so wie ich es angegangen bin
Ich hatte für jede Linie an jeden Punkt die lokale Score nur auf die Linie betrachtet ausgerechnet einmal für den Fall, dass Land unten ist und einmal für den Fall dass Wasser unten ist. Je nach Summe der Optimalen Scores dann das bessere von beiden genommen (Optimierungsmöglichkeit: Je nach Gesamtscore entscheiden). Wenn man allerdings ein bischen drüber nachdenkt merkt man schon, dass das bei der Art wie die Punkte errechnet werden nicht gut gehn kann.
Hab mir aber schon was heuristisches überlegt, was ich bei Gelegenheit vielleicht mal ausprobier wenn ich dazu komme... ich muss zugeben, dass ich die Aufgabe erst unterschätzt hab
Edit:
@ BlueCobold
Hmm aber dadurch, dass man die Grenze nur in vertikaler Richtung festlegen kann, kann man ja nicht alle Bereiche eindeutig umschließen. Außerdem wäre das "Glattheitskriterium" ja dann so oder so stark verletzt.
@ drakon
Zu der Header Sache: Mich hat folgendes verwundert: Solange ich die <string> nicht seperat eingebunden habe, hat der Compiler sich bei std::cout << std::string beschwert, nicht aber bei string selbst. Woran kann sowas liegen? Kann es sein, dass durch andere Header eine nicht vollständige Definition dessen, was <string> bietet im Umlauf ist?