Как покрыть квадратную комнату N × N наименьшим количеством квадратных плиток? (можно использовать повторно) ⇐ C++

[Anonymous]

Проблема заключается в следующем:

Покройте квадратную комнату N × N квадратными плитками (обратите внимание: плитки не обязательно должны быть одинакового размера) без перекрытия, где длина стороны каждой плитки меньше N. Каково минимальное количество плиток?
пример изображения
Мы рассчитали несколько случаев низшего порядка, и текущее минимальное значение следующее:



N
текущее лучшее решение/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 — простое число



А вот код на основе dfs:

Код: Выделить всё

#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

Подробнее здесь: [url]https://stackoverflow.com/questions/79865714/how-to-cover-an-n-%c3%97-n-square-room-with-the-least-square-tiles-could-be-reused[/url]