Как в общем работает идея дп? Представим, что мы уже решили задачу для префикса из i элементов. Теперь нужно понять, как изменится ответ, если добавить i+1-ый элемент.
Решим сначала более простую задачу, убрав ограничение "чтобы сумма всех выбранных чисел не делилась на 3". dp[i] - максимальная сумма, если рассмотрен префикс i. Теперь нужно взять один из элементов i+1-ой пары. dp[i + 1] = max(dp[i]+a[i+1].first, dp[i] + a[i+1].second). Вернемся к исходной задаче.
Теперь нужно учитывать ограничение. Для этого дополним наш dp[i]. Заведем dp[i][j]. Второй параметр(второе измерение) должен помогать удовлетворять ограничение. В этой задаче ограничение - сумма по модулю 3. Её и будем поддерживать. j = (сумма набора % 3). Тогда ответ на задачу - max(dp[n][1], dp[n][2]),потому что dp[n][0] - сумма, которая делится на 3. Снова нужно понять, как изменится ответ из текущего состояния dp[i][j], если добавится i+1-ый элемент массива. Мы можем добавить в набор либо первый, либо второй элемент пары. Если добавится, например, первый, то переход такой: dp[i+1][(j+первый_элемент)%3] ← dp[i][j].
Важно правильно проставить начальные значения! Какая сумма у пустого массива? 0 и только 0. Значит у пустого массива не бывает так, что его сумма выбранных элементов по модулю 3 равна 1 или 2. Как раз чтобы пометить состояние как невозможное, мы и присваиваем ему бесконечно малое значение. Тогда, при дальнейшем пересчете dp, обновления через это бесконечно невыгодное состояние не произойдет.
Похожие задачи: 890,108,912,955
Имеется набор данных, состоящий из N троек натуральных чисел. Составьте сумму из N чисел, выбрав из каждой тройки ровно одно число так, чтобы эта сумма не делилась нацело на k = 103 и была максимально возможной. Гарантируется, что искомую сумму получить можно.
N<=1000000
Заметим, что i+1 слой всегда пересчитывается из i-ого. Значит можно не хранить все старые слои. Так и поступим. В коде это решается просто: будем брать каждый индекс %2. И также нужно не забыть очистить i-ый слой, после того как обновили i+1-ый(так как на следующей итерации это будет уже i+2-ой слой).
Похожие задачи: 1305,1277,1396,1660