Одного неформала выгнали с работы, и теперь ему надо как-то зарабатывать себе на жизнь. Поразмыслив, он решил, что сможет иметь очень неплохие деньги на продаже собственных волос. Известно, что пункты приема покупают волосы произвольной длины стоимостью С у.е. за каждый сантиметр. Так как волосяной рынок является очень динамичным, то цена одного сантиметра волос меняется каждый день как и курс валют. Неформал является очень хорошим бизнес-аналитиком. Он смог вычислить, какой будет цена одного сантиметра волос в каждый из ближайших N дней (для удобства пронумеруем дни в хронологическом порядке от 0 до N-1). Теперь он хочет определить, в какие из этих дней ему следует продавать волосы, чтобы по истечению всех N дней заработать максимальное количество денег. Заметим, что волосы у неформала растут только ночью и вырастают на 1 сантиметр за ночь. Следует также учесть, что до 0-го дня неформал с горя подстригся наголо и к 0-му дню длина его волос составляла 1 сантиметр. язык C++

Задача сводится к тому, чтобы выбрать в какие дни продавать волосы, чтобы максимизировать прибыль. Важным моментом является тот факт, что волосы растут по 1 см за ночь, начиная с 1 см в 0-й день, и на каждом дне цена за 1 см волос может изменяться.

Подход к решению:

1. Моделируем процесс роста волос: На 0-й день длина волос — 1 см, на 1-й день — 2 см, на 2-й день — 3 см и так далее.

2. Цель: Найти такие дни, когда можно продать волосы, чтобы получить максимальную прибыль, учитывая, что цена может изменяться с каждым днем.

3. Как выбрать дни для продажи: Чтобы продать волосы с максимальной прибылью, нужно учитывать, что на каждый день неформал будет иметь все большую длину волос. Однако зарабатывать больше можно на тех днях, когда цена будет максимальной. Таким образом, нужно продать волосы в тот момент, когда цена будет на пике для данного количества сантиметров, но при этом следить за тем, чтобы не пропустить лучшие моменты.

4. Алгоритм: Чтобы максимизировать прибыль, нам нужно следить за ценой и продавать волосы в те дни, когда цена максимально выгодна, относительно того, что волосы к тому времени вырастут на определенное количество сантиметров.

Решение:

1. Изначально неформал имеет 1 см волос в день 0.
2. Для каждого дня от 1 до N-1 накапливаем количество сантиметров (они растут на 1 см каждый день).
3. На каждом дне проверяем, на сколько выгодно продать волосы, основываясь на текущей цене.
4. Продавать волосы следует тогда, когда текущая цена выгодна, и при этом этот день не должен быть позже, чем дни с еще большей длиной волос.

Примерный псевдокод:

cpp
#include 
#include 
#include 
using namespace std;
int main() {
    int N; // Количество дней
    cin >> N;
    vector<int> prices(N); // Массив цен
    for (int i = 0; i < N; i++) {
        cin >> prices[i]; // Заполняем массив цен
    }
    int max_profit = 0; // Максимальная прибыль
    int hair_length = 1; // Начальная длина волос на 0-й день
    // Идем по дням, начиная с 1-го
    for (int i = 1; i < N; i++) {
        // Смотрим на максимальную цену в будущем и решаем, стоит ли продавать
        for (int j = i; j < N; j++) {
            // Умножаем на количество сантиметров, которое было бы на момент продажи
            max_profit = max(max_profit, (j - i + 1) * prices[j]);
        }
    }
    cout << max_profit << endl;
}

В данном алгоритме берется для каждого дня и проверяется, как увеличить прибыль по максимуму.