Running#10152

Running (Razlaga rešitve)

Let $d p [i]$ be the maximum distance Bessie can run during the first $i$ minutes, provided that her fatigue level is exactly $0$ after these $i$ minutes.

Before the workout begins, $0$ minutes have passed, so we set $d p [0] = 0$ dp[0] = 0.

To compute $d p [i]$ , consider two cases:

If Bessie's fatigue level is already $0$ after the first $i - 1$ i - 1 minutes, she can simply rest for one more minute:
$d p [i] = d p [i - 1]$
dp[i] = dp[i - 1]
Suppose that Bessie spends the last $2 k$ minutes as follows:

After these $2 k$ minutes, the fatigue coefficient becomes $0$ again. Before the beginning of this block, Bessie has already completed the first $i - 2 k$ i - 2k minutes of training, so the maximum distance she could have run by this point is $d p [i - 2 k]$ dp[i - 2k].

During the first $k$ minutes of the block, Bessie runs and covers the distance

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

where

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

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

During the next $k$ minutes, Bessie rests. Her distance does not increase during the rest period, while the fatigue coefficient gradually decreases to $0$ .

Thus,

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)

Algorithm implementation

Let us define the following arrays:

$d [i]$ stores the distance Bessie will run during minute $i$ if she decides to run.
$s u m [i]$ contains the sum of the first $i$ elements of array $d$ .
$d p [i]$ contains the maximum distance Bessie can run during the first $i$ minutes, provided that her fatigue coefficient is equal to $0$ after those $i$ minutes.

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

Read the input data.

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

Compute the prefix sums of array $d$ .

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

Initialize the initial value of $d p [0]$ .

dp[0] = 0;

Sequentially compute the values $d p [1], d p [2], ..., d p [n]$ dp[1], dp[2], ..., dp[n].

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

If Bessie rests during minute $i$ , then $d p [i] = d p [i - 1]$ dp[i] = dp[i - 1].

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

At minute $i$ , a block of length $2 k$ ( $k$ minutes of running followed by $k$ minutes of rest) may end. The fatigue coefficient cannot exceed $m$ . Since the entire block must fit within these $i$ minutes, we must have $2 k \leq i$ 2k \le i.

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

Compute the distance $r u n S u m$ runSum that Bessie runs during the first $k$ minutes of the last block.

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

For the current $k$ compute the resulting optimal distance and update $d p [i]$ .

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

Print the answer.

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