Qaçış#10152

Qaçış (Həll təhlili)

$d p [i]$ — Bessinin ilk $i$ dəqiqə ərzində qaça biləcəyi maksimal məsafə olsun, bu şərtlə ki, bu $i$ dəqiqədən sonra onun yorğunluq əmsalı $0$ -a bərabər olsun.

Məşqin başlanğıcına qədər $0$ dəqiqə keçib, ona görə də $d p [0] = 0$ dp[0] = 0 qəbul edirik.

$d p [i]$ -ni hesablamaq üçün iki variantı nəzərdən keçirək:

Əgər ilk $i - 1$ i - 1 dəqiqədən sonra Bessinin yorğunluq əmsalı artıq $0$ -a bərabərdirsə, o sadəcə daha bir dəqiqə istirahət edə bilər:
$d p [i] = d p [i - 1]$
dp[i] = dp[i - 1]
Fərz edək ki, Bessi son $2 k$ dəqiqəni aşağıdakı kimi keçirib:

Bu $2 k$ dəqiqədən sonra yorğunluq əmsalı yenidən $0$ -a bərabər olur. Bu blokun başlanğıcına qədər Bessi artıq məşqin ilk $i - 2 k$ i - 2k dəqiqəsini keçirib, ona görə də bu ana qədər onun qaça biləcəyi maksimal məsafə $d p [i - 2 k]$ dp[i - 2k]-yə bərabərdir.

Blokun ilk $k$ dəqiqəsi ərzində Bessi qaçır və aşağıdakı məsafəni qət edir

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

burada

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

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

Sonrakı $k$ dəqiqə Bessi istirahət edir. İstirahət zamanı məsafə artmır, lakin yorğunluq əmsalı tədricən $0$ -a qədər azalır.

Beləliklə,

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)

Alqoritmin realizasiyası

İşçi massivləri elan edək:

$d [i]$ — əgər Bessi qaçmağa qərar verərsə, $i$ -ci dəqiqədə nə qədər məsafə qət edəcəyini saxlayır.
$s u m [i]$ — $d$ massivinin ilk $i$ elementinin cəmini saxlayır.
$d p [i]$ — Bessinin ilk $i$ dəqiqə ərzində qaça biləcəyi maksimal məsafəni saxlayır, bu şərtlə ki, bu $i$ dəqiqədən sonra onun yorğunluq əmsalı $0$ -a bərabər olsun.

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

Giriş məlumatlarını oxuyuruq.

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

$d$ massivinin prefiks cəmlərini hesablayırıq.

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

$d p [0]$ -ın başlanğıc qiymətini təyin edirik.

dp[0] = 0;

$d p [1], d p [2], ..., d p [n]$ dp[1], dp[2], ..., dp[n] qiymətlərini ardıcıl olaraq hesablayırıq.

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

Əgər $i$ -ci dəqiqədə Bessi istirahət edirsə, onda $d p [i] = d p [i - 1]$ dp[i] = dp[i - 1].

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

$i$ -ci dəqiqədə uzunluğu $2 k$ olan blok başa çatır ( $k$ dəqiqə qaçış və $k$ dəqiqə istirahət). Yorğunluq əmsalı $m$ -dən çox ola bilməz. Blokun özü bu $i$ dəqiqəyə sığmalıdır, ona görə də $2 k \leq i$ 2k \le i.

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

Son blokun ilk $k$ dəqiqəsində Bessinin qət etdiyi runSum məsafəsini hesablayırıq.

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

Cari $k$ üçün əldə edilmiş optimal məsafəni hesablayırıq və $d p [i]$ -nin qiymətini yeniləyirik.

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

Cavabı çap edirik.

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