Решение задачи Волосатый бизнес с Acmp

Без пояснения   Просмотров: 69


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


Код

#include <bits/stdc++.h>

using namespace std;

int main()
{

    int n, temp, s = 0;
    cin >> n;
    vector<int> a, c(n);
    for(int i = 0; i < n; ++i){
        cin >> temp;
        a.push_back(temp);
    }
    int pos = a.size() - 1;
    c[pos] = 1;
    for(int i = a.size() - 2; i >= 0; --i){
        if(a[pos] >= a[i])
          c[pos]++;
        else{
            pos = i;
            c[pos] = 1;
        }
    }
    int sum = 0;
    for(int i = 0; i < c.size(); ++i)
        sum += c[i] * a[i];
    cout << sum << " ";
/*
    5
    1 3 2 2 1
    1 6 6 8 5
      4 6

    9

    5
    1 9 8 2 3
    1 18 24 8 15
    24  1*/
    return 0;
}

         

Администратор Photo Автор: Администратор



Комментарии

Чтобы написать комментарии вам нужно войти в систему или зарегистрироваться