alex_agaphe

Не вижу, где тут ДП.

Вы правильно заметили, что можно вместо ai и bi рассматривать только ai^bi. Мы как будто берем все A по дефолту и каждый игрок может своим решением это стандартное действие отменить, что равносильно брать или не брать ai^bi.

Но надо заметить еще одно важное свойство (пусть di = ai ^ bi). Любое di можно заменть на di^dj (j > i) и задача остается эквивалентной. Тут каждый игрок вместо решения брать или не брать dj в зависимсоти от текущей суммы, он будет решать. делать ли статус у dj таким же как у di или нет. Ну или, рассуждение как выше, стандартное действие - брать dj если di было взято. Каждый игрок может своим решением это действие отменить.

А это уже очень похоже на вычитание линейных уравнений друг из друга в методе гауса. Можно этим заняться и привести Di к виду, где для каждого разряда мы найдем "базисный вектор" и единица будет стоять только в нем, а во всех остальных числах на этом разряде будет стоять 0. Для каких-то разядов мы может такого не найдем, там может быть много единиц, но все они будут в базисных векторах для каких-то других разрядов. При чем начинайте фиксировать базис с максимальных разрядов. Тогда у вас будут какие-то базисные разряды, и не базисные, которые однозначно определяются базисными и меньше их.

Т.е. идете с конца по массиву D, из текущего числа xor-ите все базисные вектора. если стоит единица в нужном разряде. Если там остался не ноль, добавляете это число в базис для старшего бита.

И тут уже сразу ясно, надо ли какое-то Di брать или нет. Каждый игрок знает, хочет ли он этот разряд в конце сделать 1 или 0 (в зависимости от его цели и того, стоит ли 1 в xor всех A в этом разряде).

Вот и все. Никакого ДП.

В правильном решении 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'].

Если это задача такая, то я предполагаю, что там надо удалить минимальное количество скобок, чтобы последовательность стала правильной. Можно только удалять скобки, потому что вместо любого добавления скобки, можно просто вторую пару удалять. Количество действий не изменится. Правда, в ваших примерах оно удалит все скобки.

Тут можно решать динамическим программированием. Пусть F(l,r) - минимальное количество операций удаления, чтобы сделать из строки с l по r правильную скобочную последовательность.

База - если l..r - пустая строка - ответ 0.
Иначе надо рассматривать варианты, что будет с последним символом. Если в конце стоит открывающая скобка, то ее надо удалить - других вариантов нет: F(l,r) = 1+F(l,r-1).

Если же там закрывающая скобка, то есть 2 варинта: или этот символ удаляем, или берем в ответ. В первом варианте ответ такой-же, как выше. Во втором - надо перебрать, а какой же символ в строке будет открывающей скобкой для данной. Пусть это символ i (там должна стоять открывающая скобка того же типа). Тогда ответ F(l,i-1)+F(i+1,r-1) - ведь части перед парой скобок и внутри их должны тоже быть правильными последовательностями.
Из всех вариантов надо выбрать минимальный - это и будет ответ для текущего состояния.

Если хотите восстанвливать саму последовательность, то надо при сохранении минимума еще и сохранять в отдельном двумерном массиве - какой именно из вариантов был выбран (дропнуть последний символ, или какой символ взять ему в пару).

Ответ к задаче - F(1,n) - для всей строки.

Это решение потребляет O(n^2) памяти и занимает O(n^3) времени.

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

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

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

НОД

GPT ИИ к сожалению это именно магия, на основе детерминированной математики получили не детерминированный результат, который симулирует человеческий ИИ, и который даже можно попытаться использовать

Сильные версии gpt (старше openai:gpt3.5) можно попросить словами дать ответ в json, и так же словами или стандартными способами описания форматов, прямо в запросе... результат будет с некоторой вероятностью не верным, это фича и боль gpt

Некоторые провайдеры позволяют указать, например openai structured outputs или у открытой llama.cpp grammars (это фича программы для запуска ИИ а не моделей), позволяющие описать ограничения на формат ответа, соответственно для json есть готовые описания, можно даже ограничить в значениях (там есть свои нюансы, так как одно и то же слово можно описать разными токенами), это позволит гвоздями прибить ответ модели к требуемому формату, ценою понижения качества результата (но в каких то случаях - повышения), ответ можно получить только экспериментами на своих данных.

По поводу как решать задачи с поиском слов, приведи по больше примеров, наилучший на текущий момент из подходов, это multi shot, где ты даешь модели последовательностью "системный промпт - пример вопрос - пример ответ - пример вопрос - пример ответ - вопрос -" и она выдает ответ, чем больше и лучше будут примеры, тем выше качества ответа. Системный промпт должен быть максимально подробным и содержать всю необходимую для принятия решения информацию, не надеясь на знания модели (их у нее так много что это мешает)

Осторожно, gpt очень плохо работают с данными, когда нужно из большого объема вытаскивать большой объем, например формировать список, чем больше будет данных, тем выше вероятность что модель что то пропустит или еще хуже, добавит что то от себя. Лучшим способом будет режим чата - когда после системного промпта идут которткий кусок данных, и в виде ответа модели - сообщение о наличии или отсутствии в нем искомых данных, соответственно подавая исходные данные по частям, модель будет давать ответ тут же, а так же видеть предыдущие варианты как пример multishot... Но чем больше данных будет в чате, тем хуже может быть, так как данные могут быть однобокими, что может испортить качество результата.. т.е. нужен механизм фильтрации, какие предыдущие данные сохранять в чате (критерий - уникальность, разруливание спорных случаев, исправление ошибок модели при ручной модерации и т.п.). Так как большинство провайдеров умеют кешировать начало промпта (тарифицируя эти токены значительно дешевле), такой подход может быть значительно эффективнее чем если делать один запрос со всеми входными данными.

Наилучший на текущий момент способ улучшения качества ответа - за счет экспоненциального роста затрат, это повтор вопроса (при случайном seed), сбор статистики ответов и выбор наиболее вероятного. Т.е. делаешь 16 одинаковых запросов, получаешь 16 разных ответов, выбираешь повторяющиеся чаще всего как верный ответ... увеличивая в 2 раза количество запросов, ты поднимешь качество ответа на условный процент, рост не бесконечный, обычно где то на тысячах попытках рост из линейного становится 'пологим'. Не нужно надеяться на то что если ответ - в последнем токене и можно просто тысячу раз его сгенерировать (кстати это можно вытащить из logits токена, там прямо список вероятностей лежит), важно именно рассуждения по разному запускать.

Второй способ улучшения качества ответа достаточно абсурдный, - используя модели с возможностью к рассуждениям (reasoning или thinking) можно, увеличивая размер области рассуждений в токенах, можно так же увеличивать качество, вот пример зависимости от последней открытой qwen3 moe модели: