Одного неформала выгнали с работы, и теперь ему надо как-то зарабатывать себе на жизнь. Поразмыслив, он решил, что сможет иметь очень неплохие деньги на продаже собственных волос. Известно, что пункты приема покупают волосы про...

Question

Одного неформала выгнали с работы, и теперь ему надо как-то зарабатывать себе на жизнь. Поразмыслив, он решил, что сможет иметь очень неплохие деньги на продаже собственных волос. Известно, что пункты приема покупают волосы про...

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

Гость

Ответ(ы) на вопрос:

Accepted Answer

#include #include #include using namespace std; map, int> saved_rec; map> path; int max_cost(const vector& 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 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 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); }