Wataru

Сначала переформулируем задачу - надо найти минимальное количество клеток с пауками в конце. Каждая клетка доски должна быть "покрыта": или быть с пауками, или быть соседней с клеткой с пауками.

У задачи много решений.
Во-первых, можно порисовать частные случаи с маленькими досками и найти формулу.
Для мелких значений там частные случаи, а для больших можно получить формулу.

Что-то вроде такого расположения работает на больших досках:

*...*...*
..*...*..

Во-вторых, можно решать через графы. Пусть каждая клетка - вершина графа. Ребра между соседними клетками. Заметим, что граф - двудольный (шахматная раскраска доски - это и есть 2 доли). Исходная задача поиска минимального количества клеток с пауками, это фактически задача поиска контролирующего множества вершин: каждая клетка должна или быть во множестве, или быть соседней с клеткой из множества. В двудольном графе эта задача равнасильна поиску максимального паросочетания. Это решение за O(n^2m^2).

Если хотите ДП, то перед переходами надо определиться с состояниями. Ясно, что будет какое-то ДП по профилю. Будем целиком покрывать сколько-то первых строк, а состояние последней строки хранить в маске. Поскольку каждая клетка может быть покрыта как снизу, так и сверху, то в состоянии надо держать состояние 2 последних строк.
Например, состоянием может быть f(k,m1,m2) - расставили пауков в клетках их первых k строк. Считаем минимальное количество пауков. Первые k-1 целиком покрыты, строка k покрыта маской m1, а строка k+1 - маской m2. База f(0,0,0) = 0, f(0, m1, m2) = infinity. Ответ будет в min_m2 (f(n, 2**m-1, m2)).

Переход снизу вверх: перебираем, куда мы ставим пауков в строке k+1. При этом важно, что бы строка k оказалось целиком покрыта. Пресчитываем маску в строке k+1, а маска в строке k+2 - это будет куда мы поставили пауков:
F(k,m1,m2) --> F(k+1, m2 | m3 | (m3 << 1) | (m3 >> 1), m3), для всех m3, таких что m3 | m = 2**m-1

Это будет решение за O(n6^m).

Циклы в питоне - это ужасно медленно, да. Не лучший язык для написания числодробилки.

Еще, оффтопик, база даных тут совсем не нужна. Достаточно выводить числа на экран или в текстовый файл. так быстрее будет.

У вас самый наивный перебор в лоб, его можно ускорить. Сначала сгенерируйте все кубы и схраните их в массив. Их будет примерно кубический корень из |MAX_VAL-MIN_VAL| - это достаточно маленькая величина.

Теперь задача: найти 3 числа в массиве, дающих в сумме число из массива. Это все еще O(n^3), если исползовать 4 индекса. Но можно ускорить решение методом "встреча по середине".
Вместо A+B+C=D из массива будем искать A+B=C-D. Для этого переберем все пары чисел, подсчитаем их сумму и сохраним в dict() вместе со списком индексами этих чисел (список всех пар, дающих эту сумму). Потом опять переберем все пары, подсчитаем их разность и посмотрим в словаре, а была ли пара с такой же суммой. Если была - вот мы нашли 4 числа, таких что A+B=C-D. извлекаем корни и выдаем это в ответ.
Это будет уже O(n^2) - заметно быстрее.

DeepSeek галлюционирует. Временные объекты живут до конца выражения. unique_ptr начнет уничтожение после выполнения всего выражения.

Вот ссылки на стандарт:

make_unique<> является prvalue: https://en.cppreference.com/w/cpp/language/value_c...

prvalue: a function call or an overloaded operator expression, whose return type is non-reference

В момент вызова происходит материализация временного объекта: https://en.cppreference.com/w/cpp/language/lifetime

Temporary objects are created ... in the following situations:
when performing member access on a class prvalue.

Там же написано:

All temporary objects are destroyed as the last step in evaluating the full-expression

Т.е. возвращенный make_unique объект будет уничтожен только в конце строки.

Вам не нужно их симулировать. Вам нужно их подсчитать. Есть же формулы, на той же википедии посмотрите. Через факториалы. Считается это несколькими циклами прямо в одной переменной. Только аккуратно с большими числами, могут быть переполнения, если у вас нет длинной арифметики в языке.

Edit: Если, все-таки, хочется именно случайно сочетание сгенерировать, то вот алгоритм, основанный на reservoir sampling:

int taken = 0;
for (int i = 0; i < n; ++i) {
  if (rand()*(n-i) < k-taken) {
    ++taken;
    // Взять элемент i.
  }
}

Для восстановления вам нужен второй массив, где вы храните одно из 3 значений - в какой из трех наборов идет i-ая гиря. Когда считаете dp и пишите, что можно составить i, w1, w2 вы же эти значения получили куда-то поместив последний элемент. У вас или к w1 что-то было прибавлено, или к w2, или никуда. Это 3 варианта.

При восстановлении начните с N, sum/3, sum/3 и в цикле вычитайте 1 из первого индекса и вес i-й гири или не вычитайте или вычитайте из одного из весов, в зависимости от сохраненного знаяения во втором массиве.

Можно вместо второго массива в dp хранить 0, если это состояние невозможно и или номер кучки для последней гири.

В дизайне интерфейса можно передавать и копию и rvalue refernce. Что выбрать - решать вам, как создателю интерфейса. Если у вас предполагаются использование функций/лямбд без тяжелого состояния (связанные аргументы по значению), то копирование дешевое и не надо его вводить. rvalue reference всегда дешево, но у вас нельзя будет переиспользовать предикат между разными вызовами.

В функциях из algorithm используется передача по значению, что бы не ограничивать пользователя. Вы можете один раз написать нужный вам предикат и передавать его во все вызовы. Плюс исторически так сложилось. Когда оно все созадавалось, никаких rvalue reference и не было. Потом их добавлять и не стали, потому что в самом частом случае, если лямбду прямо в аргументах задавать, то она практически бесплатно передастся.

Там не используется передача по ссылке (lvalue reference), потому что это не так универсально в шаблоне. Если у вас какой-то const предикат, вы его в reference не передадите. А делать const & в интерфейсе нельзя, вдруг у вас предикат не константный?

И, если вы все-таки хотите передать ссылку, то можно передать std::ref(pred), тогда в шаблоне выведется передача по ссылке.

Тут поможет только практика. Чтобы научиться решать задачи - надо много задач решить. Если не можете какую-то задачу решить сами, читайте разбор или чужие решения, пока не поймете, что там происходит. И потом обязательно реализуйте решение сами, не перепечатывая готовое.

Хорошие книги: Кнут "искусство програмирования", Кормен "алгоритмы. Построение и анализ", Бхаргава "Грокаем алгоритмы". Старайтесь прорешивать все упражнения в этих книгах. Но прочитав их вы задачи решать не научитесь, а лишь подтянете базу.

Похоже на ошибку оформления. Это должен быть вызов функции. В тексте выше даже написано про вызов.

Тут автор считает, что сначала выполнится new A(), потом new B(), потом конструктор unique_ptr. Если исключение бросит B(), то действительно будет утечка памяти. Объект A, полученный через new умрет еще до оборачивания в unique_ptr. Такой сырой указатель автоматически не удалится.

Такая последовательность невозможна c С++17:

In a function call, value computations and side effects of the initialization of every parameter are indeterminately sequenced with respect to value computations and side effects of any other parameter.

Evaluations of A and B are indeterminately sequenced : they may be performed in any order but may not overlap: either A will be complete before B, or B will be complete before A. The order may be the opposite the next time the same expression is evaluated.

Но до C++17, действительно, компилятор может перемешать вычисления аргументов как угодно.

У вас неинициализированные переменные mini и maxi. И они используюся такими в сравнениях. Это Undefined Behavior и на разных компьютерах может вести себя по разному. И если вам не повезет и, например, mini окажется каким-то очень маленьким числом, то у вас выдаст не правильный ответ.

Вам надо разбить массив на K как можно более равных частей?

Если длина массива N, то все куски будут длиной хотя бы floor(N/K), и ровно N%K будут иметь на 1 элемент больше. Вроде, если у вас 10 элементов надо на 3 потока разделить, то будут длины {4, 3, 3}. А если 15 на 4, то {4, 4, 4, 3}

Так что i-ый кусок будет начинаться с позиции (N/K)*i + min(i, N%K) и иметь длину N/K + ((i < N%K) ? 1 : 0).

Чуть проще формулы, если вы эти позиции явно в массиве получите, а не будете каждую отдельно считать:

int start[K], end[K];
int prev = -1;
for (int i = 0; i < K; ++i) {
  int len = N/K + ((i < N%K) ? 1 : 0);
  start[i] = prev + 1;
  end[i] = start[i] + len;
  prev = end[i];
}

Никак не называется. Можно структуры комбинировать для ваших задач, но это частные случаи применения структур, не настолько частые, чтобы давать этой комбинации какое-то имя. Если уж хочется назвать это как-то, то это все еще будет хеш-таблица с какими-то вспомагательными пристройками для каких-то дополнительных нужных вам свойств (итерация).

И вообще, у вас тут намудрено, почему нельзя сделать просто:
let objects: HashMap<Uuid, Object>;

Тут все такой же O(1) доступ к элементу по id. Зачем вам массив? Вы там добились простой и cache-friendly итерации по всем объектам? Не факт, что это уже не реализовано внутри HashMap. По крайней мере во многих языках можно проитерироваться по всем объектам в стандартной хеш-таблице.

Зато у вас там удаление элемента - это что-то сложное. Особенно, если вы не хотите избежать фрагментации и неиспользованного места в массиве.

Вообще, не вижу противоречия. У вас же там tfunc&&, его вы пытаетесь к void* привести и к нему применяете remove reference.

Попробуйте в ваш static assert добавить std::move и он обвалится.

В правильном решении dp[i][k][t] должно обозначать максимальную возможную стоимость объектов, среди превых i, такое что суммарная энергия и время у них t и k. Или -inf, если такое набрать невозможно.

Пересчет: dp[i][k][t] = max(dp[i-1][k][t], dp[i-1][k-K[i-1]][t - T[i-1]]) (второй вариант считаем, только если k>= K[i-1], t>= T[i-1].

База: dp[0][0][0] = 0, dp[0][k][t] = -inf.

Ну и ответ - max_{k, t} Dp[n][k][t].

Раз надо выводить и сами объекты, то надо еще запоминать, откуда был переход, т.е. еще один трехмерный массив bool, Где вы будете хранить True, если пересчитали через + x['v'].