Ask Your Question

Revision history [back]

click to hide/show revision 1
initial version

posted 2015-03-17 16:36:30 +0100

generuješ si obdélníky délky 1x1 až NxN
pak je posouváš do všech míst kam to jde
a pro každé posunutí sečteš prvky uvnitř obdélníku.

A ty hledáš největší obdélníky, který má ten součet menší nebo roven maxCost

generuješ si obdélníky délky 1x1 až NxN
pak je posouváš do všech míst kam to jde
a pro každé posunutí sečteš prvky uvnitř obdélníku.

A ty hledáš největší obdélníky, obdélník, který má ten součet menší nebo roven maxCost

EDIT Níže uvedené řešení není O(n^4)

generuješ obdélníky délky 1x1 až NxN
pak je posouváš do všech míst kam to jde
a pro každé posunutí sečteš prvky uvnitř obdélníku.

A ty hledáš největší obdélník, který má ten součet menší nebo roven maxCost

EDIT2 Nejprve je to potřeba předpočítat tak, že si pro každý obdelník spočítáš součet plochy vlevo nad ním.
image description
A = C+B-D

A pak si projdeš všechny obdélníky tím způsobem, že si každý obdélník spočítáš takto:
image description
žlutá plocha = D - C - B + A

EDIT Níže uvedené řešení není O(n^4)

generuješ obdélníky délky 1x1 až NxN
pak je posouváš do všech míst kam to jde
a pro každé posunutí sečteš prvky uvnitř obdélníku.

A ty hledáš největší obdélník, který má ten součet menší nebo roven maxCost