Corsa#10152

Corsa (Editoriale)

Sia $d p [i]$ — la distanza massima che Bessie può percorrere nei primi $i$ minuti, a condizione che dopo questi $i$ minuti il suo coefficiente di stanchezza sia uguale a $0$ .

Prima dell'inizio dell'allenamento sono trascorsi $0$ minuti, quindi poniamo $d p [0] = 0$ dp[0] = 0.

Per calcolare $d p [i]$ consideriamo due varianti:

Se dopo i primi $i - 1$ i - 1 minuti il coefficiente di stanchezza di Bessie è già uguale a $0$ , allora essa può semplicemente riposare per un altro minuto:
$d p [i] = d p [i - 1]$
dp[i] = dp[i - 1]
Supponiamo che gli ultimi $2 k$ minuti Bessie li abbia trascorsi nel modo seguente:

Dopo questi $2 k$ minuti il coefficiente di stanchezza torna ad essere uguale a $0$ . Prima dell'inizio di questo blocco, Bessie ha già trascorso i primi $i - 2 k$ i - 2k minuti dell'allenamento, quindi la distanza massima che poteva percorrere fino a quel momento è uguale a $d p [i - 2 k]$ dp[i - 2k].

Durante i primi $k$ minuti del blocco Bessie corre e percorre la distanza

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],

dove

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

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

Nei successivi $k$ minuti Bessie riposa. Durante il riposo la distanza non aumenta, mentre il coefficiente di stanchezza diminuisce gradualmente fino a $0$ .

Così,

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)

Implementazione dell'algoritmo

Dichiariamo gli array di lavoro:

$d [i]$ memorizza quanto Bessie percorrerà nel minuto $i$ , se decide di correre.
$s u m [i]$ contiene la somma dei primi $i$ elementi dell'array $d$ .
$d p [i]$ contiene la distanza massima che Bessie può percorrere nei primi $i$ minuti, a condizione che dopo questi $i$ minuti il suo coefficiente di stanchezza sia uguale a $0$ .

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

Leggiamo i dati in ingresso.

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

Calcoliamo le somme prefisse dell'array $d$ .

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

Inizializziamo il valore iniziale $d p [0]$ .

dp[0] = 0;

Calcoliamo in sequenza i valori $d p [1], d p [2], ..., d p [n]$ dp[1], dp[2], ..., dp[n].

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

Se al minuto $i$ Bessie riposa, allora $d p [i] = d p [i - 1]$ dp[i] = dp[i - 1].

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

Al minuto $i$ si conclude un blocco di lunghezza $2 k$ ( $k$ minuti di corsa e $k$ minuti di riposo). Il coefficiente di stanchezza non può superare $m$ . Poiché il blocco stesso deve rientrare in questi $i$ minuti, allora $2 k \leq i$ 2k \le i.

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

Calcoliamo la distanza runSum, che Bessie ha percorso nei primi $k$ minuti dell'ultimo blocco.

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

Per il $k$ corrente calcoliamo la distanza ottimale ottenuta e aggiorniamo il valore di $d p [i]$ .

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

Stampiamo la risposta.

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