Біг#10152

Біг (Розбір)

Нехай $d p [i]$ — максимальна відстань, яку Бессі може пробігти за перші $i$ хвилин за умови, що після цих $i$ хвилин її коефіцієнт втоми дорівнює $0$ .

До початку тренування пройшло $0$ хвилин, тому покладемо $d p [0] = 0$ dp[0] = 0.

Для обчислення $d p [i]$ розглянемо два варіанти:

Якщо після перших $i - 1$ i - 1 хвилин коефіцієнт втоми Бессі вже дорівнює $0$ , то вона може просто відпочити ще одну хвилину:
$d p [i] = d p [i - 1]$
dp[i] = dp[i - 1]
Припустимо, що останні $2 k$ хвилин Бессі провела наступним чином:

Після цих $2 k$ хвилин коефіцієнт втоми знову стає рівним $0$ . До початку цього блоку Бессі вже провела перші $i - 2 k$ i - 2k хвилин тренування, тому максимальна відстань, яку вона могла пробігти до цього моменту, дорівнює $d p [i - 2 k]$ dp[i - 2k].

Протягом перших $k$ хвилин блоку Бессі біжить і долає відстань

d [i - 2 k + 1] + d [i - 2 k + 2] + ... + d [i - k] = s u m [i - k] - s u m [i - 2 k],

d[i − 2k + 1] + d[i − 2k + 2] + ... + d[i - k] = sum[i - k] - sum[i - 2k],

де

s u m [i] = d [1] + d [2] + ... + d [i]

sum[i] = d[1] + d[2] + ... + d[i]

Наступні $k$ хвилин Бессі відпочиває. За час відпочинку відстань не збільшується, а коефіцієнт втоми поступово зменшується до $0$ .

Таким чином,

d p [i] = max d p [i - 1], 1 \leq k \leq m 2 k \leq i max (d p [i - 2 k] + s u m [i - k] - s u m [i - 2 k])

dp[i] = \max\left(dp[i-1], \max_{\substack{1 \le k \le m \\ 2k \le i}} \left(dp[i-2k] + sum[i-k] - sum[i-2k]\right)\right)

Реалізація алгоритму

Оголосимо робочі масиви:

$d [i]$ зберігає, скільки Бессі пробіжить на хвилині $i$ , якщо вона вирішить бігти.
$s u m [i]$ містить суму перших $i$ елементів масиву $d$ .
$d p [i]$ містить максимальну відстань, яку Бессі може пробігти за перші $i$ хвилин, за умови, що після цих $i$ хвилин її коефіцієнт втоми дорівнює $0$ .

#define MAX 10001
int d[MAX], sum[MAX], dp[MAX];

Зчитуємо вхідні дані.

scanf("%d %d", &n, &m);
for (i = 0; i < n; i++)
  scanf("%d", &d[i]);

Обчислюємо префіксні суми масиву $d$ .

sum[0] = 0;
for (i = 1; i <= n; i++)
  sum[i] = sum[i - 1] + d[i - 1];

Ініціалізуємо початкове значення $d p [0]$ .

dp[0] = 0;

Послідовно обчислюємо значення $d p [1], d p [2], ..., d p [n]$ dp[1], dp[2], ..., dp[n].

for (i = 1; i <= n; i++)
{

Якщо на хвилині $i$ Бессі відпочиває, то $d p [i] = d p [i - 1]$ dp[i] = dp[i - 1].

  dp[i] = dp[i - 1];

На хвилині $i$ завершується блок довжини $2 k$ ( $k$ хвилин бігу та $k$ хвилин відпочинку). Коефіцієнт втоми не може перевищувати $m$ . Оскільки сам блок повинен вміщатися в ці $i$ хвилин, то $2 k \leq i$ 2k \le i.

  for (k = 1; k <= m && 2 * k <= i; k++)
  {

Обчислюємо відстань runSum, яку Бессі пробігла за перші $k$ хвилин останнього блоку.

    int runSum = sum[i - k] - sum[i - 2 * k];

Для поточного $k$ обчислюємо отриману оптимальну відстань і оновлюємо значення $d p [i]$ .

    int temp = dp[i - 2 * k] + runSum;
    if (temp > dp[i]) dp[i] = temp;
  }
}

Виводимо відповідь.

printf("%d\n", dp[n]);