Mənfəətin maksimumlaşdırılması#11480

Mənfəətin maksimumlaşdırılması (Həll təhlili)

Güman edək ki, $p_{0}, p_{1}, ..., p_{n - 1}$ p_0, p_1, ..., p_{n-1} — günlər üzrə səhm qiymətləridir. $d p_{i} = ma x (p_{i}, ..., p_{n - 1})$ dp_i = max(p_i, ..., p_{n-1}) hesablayaq — $p$ massivinin sufikslərində maksimum qiyməti. Əgər $i$ -ci gündə səhm $p_{i}$ p_i qiymətinə alınarsa, gələcəkdə onu ən yüksək $d p_{i}$ dp_i qiymətinə satmaq əlverişli olacaq, və mənfəət $d p_{i} - p_{i}$ dp_i - p_i təşkil edəcək. Ümumi mənfəəti hesablamaq qalır, bərabərdir:

i = 0 \sum n - 1 (d p_{i} - p_{i})

\sum_{i=0}^{n - 1} (dp_i - p_i)

Misal

İkinci testi nəzərdən keçirək. Səhm qiymətləri massivində sufikslər üzrə maksimumu hesablayaq.

Məsələn, birinci gündə səhmi $p_{1} = 2$ p_1 = 2 qiymətinə alırıq və gələcəkdə onu $d p_{1} = 9$ dp_1 = 9 qiymətinə satırıq (satış üçüncü gündə həyata keçiriləcək).

Ümumi mənfəət $4 + 7 + 3 + 0 + 7 + 2 + 3 + 0 + 0 = 26$ 4 + 7 + 3 + 0 + 7 + 2 + 3 + 0 + 0 = 26 təşkil edəcək.

Alqoritmin həyata keçirilməsi

Giriş məlumatlarını oxuyuruq.

scanf("%d", &n);
p.resize(n);
dp.resize(n);
for (i = 0; i < n; i++)
  scanf("%d", &p[i]);

$d p_{i} = ma x (p_{i}, ..., p_{n - 1})$ dp_i = max(p_i, ..., p_{n-1}) hesablayaq.

dp[n - 1] = p[n - 1];
for (i = n - 2; i >= 0; i--)
  dp[i] = max(p[i], dp[i + 1]);

Ümumi mənfəət $r es$ -i hesablayaq. $i$ -ci gündə səhmi $p_{i}$ p_i qiymətinə alırıq və gələcəkdə onu $d p_{i}$ dp_i qiymətinə sataraq $d p_{i} - p_{i}$ dp_i - p_i mənfəəti əldə edirik.

res = 0;
for (i = 0; i < n; i++)
  res = res + dp[i] - p[i];

Nəticəni çapa veririk.

printf("%lld\n", res);

Python həyata keçirilməsi

Giriş məlumatlarını oxuyuruq.

n = int(input())
p = list(map(int, input().split()))

$d p_{i} = ma x (p_{i}, ..., p_{n - 1})$ dp_i = max(p_i, ..., p_{n-1}) hesablayaq.

dp = [0] * n
dp[n - 1] = p[n - 1]
for i in range(n - 2, -1, -1):
  dp[i] = max(p[i], dp[i + 1])

res = 0
for i in range(n):
  res += dp[i] - p[i]

Nəticəni çapa veririk.

print(res)