Wie deckt man einen N × N quadratischen Raum mit den wenigsten quadratischen Fliesen ab? (könnte wiederverwendet werden) ⇐ C++

[Anonymous]

Das Problem ist:

Bedecken Sie einen N × N quadratischen Raum mit quadratischen Kacheln (die Kacheln müssen nicht alle die gleiche Größe haben) ohne Überlappung, wobei die Seitenlänge jeder Kachel ganzzahlig und kleiner als N ist.
Wie viele Kacheln sind mindestens erforderlich?
sample_of_cover.jpg
Wir haben manuell einige Fälle niedrigerer Ordnung gezeichnet, und die aktuelle Mindestanzahl ist wie folgt folgt:



N
aktuelle Mindestanzahl/f(N)




3
6


4
4


5
8


6
4


7
9


8
4


9
6


10
4


11
11


13
13


17
12


k*n
f(n)|n ist eine Primzahl



Und hier ist ein Code, der auf dfs basiert. Dieser Code ist sicher und in der Lage, die optimale Lösung zu liefern, ist jedoch wenig effizient und wird daher nur als Referenz bereitgestellt. Wir haben an diesem Code nicht viele spezielle Optimierungen vorgenommen, weil wir glauben, dass er unsere Anforderungen nicht vollständig erfüllen wird, insbesondere wenn N eine große PRIME-Zahl ist (z. B. 73).
Wir suchen nach Antworten in Form von effizientem Code (O[n^3] oder niedriger) oder einer klaren und strengen mathematischen Argumentation, die dabei helfen kann, die Dinge voranzubringen.

Code: Select all

#include 
using namespace std;
#define ll long long

const int inf=0x3f3f3f3f;

int vis[105][105];
int n;

bool judge(int i,int j,int k)
{
bool ans=true;
for(int ii=i;ii