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

#include <iostream>
#include <map>
#include <vector>

using namespace std;

map<pair<int, int>, int> saved_rec;
map<int, pair<int, int>> path;

int max_cost(const vector<int>& cost, int day, int length)
{
   if (day + 1 < length)
       length = day + 1;
   if (saved_rec[make_pair(day, length)] != 0)
       return saved_rec[make_pair(day, length)];

   int tmp_cost, max = cost[day] * length, max_i = length;

   if (day != 0)
       for (int i = 0; i <= length; ++i)
       {

           tmp_cost = max_cost(cost, day — 1, length-i)
               + cost[day] * i;
           if (tmp_cost > max)
           {
               max = tmp_cost;
               max_i = i;
           }
       }

   saved_rec[make_pair(day, length)] = max;
   if (max_i != 0)
       path[max] = make_pair(day, max_i);
   return max;
}

int main()
{
   vector<int> cost = { 6, 2, 5, 4, 5, 3, 3, 4};

   int last_day_num = cost.size() — 1,
       total_length = cost.size(),
       max;

   max = max_cost(cost, last_day_num, total_length);
   cout << «Max profit: » << max << endl;

   pair<int, int> day_count;
   int sm = 0;

   do
   {
       day_count = path[max];
       cout << «Day: » << day_count.first << ", length: " << day_count.second << endl;
       max -= cost[day_count.first] * day_count.second;
   } while (max != 0);
}