Тяжелое положение при планировании парада Пейтона (HPI, 2019)

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

К сожалению, они обнаружили, что во время ожидания в очереди у местных жителей возникли споры со своими соседями по очереди, так что местный i отказывается выставлять свой поплавок на параде с местным i-1 или местным i + 1.

Пейтон оценил каждый поплавок i по качеству Q_i (некоторые настолько плохо построены, что их качество отрицательное). Общее качество парада равно сумме качества включенных поплавков.

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

Чтобы увидеть или попытаться решить проблему полностью, зарегистрируйтесь здесь, затем нажмите здесь.

Решение

Ваша первая интуиция может заключаться в том, чтобы попробовать две комбинации, поплавки с четными номерами и поплавки с нечетными номерами, и выбрать ту комбинацию, которая имеет более высокое совокупное качество. Однако это не работает в таких случаях, как 4 числа с плавающей запятой с оценкой 2 1 1 2 (вы бы выбрали последние два).

Вместо этого мы можем думать об этом как о проблеме динамического программирования. Предположим, мы можем вычислить максимальное качество, учитывая только первые X чисел с плавающей запятой. Назовем это значение DP [X]. Мы можем быть уверены, что для всех X DP [X] ≥ DP [X-1]. Это связано с тем, что любой набор поплавков, который может быть сформирован из первых X-1 поплавков, также может быть создан из первых X поплавков. Таким образом, чтобы вычислить значение DP [X], нам нужно рассмотреть только два случая, включая X-й float, который даст качество Q [X] + DP [X-2], и не включая X-й float, который даст качество DP [X-1]. Любое из этих значений может быть больше другого, поэтому мы должны вычислить DP [X] как

DP[X] = MAX(DP[X - 2] + Q[X], DP[X - 1])

Мы знаем, что начальное значение DP [0] = 0 и DP [1] = Q [1]. Отсюда мы можем рассчитать все более поздние значения. Таким образом, наш ответ, максимальное качество, учитывая первые N чисел с плавающей запятой, можно найти как DP [N].

Ниже мое решение на C ++.

#include<iostream>
using namespace std;
int n;
int arr[100002];
int dp[100002];
int main() {
   cin >> n;
   for (int i = 1; i <= n; i++) cin >> arr[i];
   dp[1] = max(0, arr[1]);
   for (int i = 2; i <= n; i++)
      dp[i] = max(dp[i - 2] + arr[i], dp[i - 1]);
   cout << dp[n] << endl;
}