Волосатый бизнес (разомнёмся и разбогатеем), задачка для ума

int max=cost[0];
int out;
int inp=0;
int sum=0;
bool d=false;
do
{
for (int i=inp;i<N;i++)
{
if(max<cost)
{
max=cost;
out=i;
}
}
sum+=(out-inp)*cost[out];
max=0;
if (out!=N-1)
inp=out+1;
else
d=true;
}while(d)
return sum;

ну гдето так, нет возможности проверить

Кажись, задача скорее математическая, чем програмерская, и наверняка решение лежит в области оптимизационной задачи линейного программирования. Кажись.

Да, действительно, математика очень помогла. Хотя обошлось без линейного программирования - всё оказалось гораздо проще.

Есть "тупое", прямое решение - перебор всех вариантов. Вариантов, очевидно, 2^N, где N - количество дней. Тогда сложность алгоритма составит соответственно O (2^N), т. е. при увеличении кол-ва дней на 1 программа будет работать вдвое дольше.
Мой пень-4 2,4 ГГц вычислял 0,3 сек. для 20 дней, 5 минут для 30 дней, а 100 дней будет вычислять несколько триллионов лет.

Однако займемся математикой:
1. Очевидно, в последний день в любом случае надо стричься. Т. е. последняя стрижка будет в последний день.

2. Предположим, мы нашли, что в некоторый j-й день выгодно будет постричься. Посмотрим, выгодно ли стричься в i-й день (i < j). Возникает два варианта:

2а. До i-го дня стрижек нет. Тогда длина волос в i-й день составит i+1, цена стрижки соответственно (i+1) * Ci. К j-му дню волосы вырастут длиной j-i. Соответственно, прибыль, которую мы получим за две стрижки (i-й день и j-й день) составит
s1 = (i+1) * Ci + (j-i) * Cj
А если мы не будем стричься в i-й день, прибыль составит
s0 = (j+1) * Cj
Разность между этими величинами
s1 - s0 = i * Ci + Ci + j * Cj - i * Cj - j * Cj - Cj = i*Ci + Ci - i*Cj - Cj = (i+1) * (Ci - Cj)
Нас интересует только знак этой разницы - если она положительна, стричься в i-й день выгодно, если нет - не выгодно. Знак разницы зависит только от знака величины Ci - Cj, т. е. в i-й день стричься выгодно тогда и только тогда, когда Ci > Cj.

2b. До i-го дня есть стрижка, которая происходит в k-й день (т. е. k < i). Тогда суммарная прибыль, зарабатываемая в i-й и j-й дни, составит, если стричься в i-й день:
s1 = (i-k) * Ci + (j-i) * Cj
А если не стричься:
s0 = (j-k) * Cj
Опять же, оценим разность:
s1 - s0 = i*Ci - k*Ci + j*Cj - i*Cj - j*Cj + k*Cj = i * (Ci - Cj) - k (Ci - Cj) = (i-k) * (Ci - Cj)
Снова, поскольку k < i, знак этой разницы зависит только от Ci - Cj, т. е. опять же стричься в i-й день выгодно тогда и только тогда, когда Ci > Cj.

Как видим, в любом случае единственным критерием оценки выгодности стрижки в i - й день является её стоимость.

Отсюда алгоритм. Из (1) следует, что в последний день стричься надо в любом случае. Теперь перебираем дни с конца к началу и, как только встретим день с ценой стрижки выше, чем цена последнего дня, в этот день также стрижемся и одновременно запоминаем эту цену. Вновь движемся к началу и, как только встретится день с ценой стрижки выше, чем та цена, что мы запомнили, стрижемся в этот день и т. д.

Сложность такого алгоритма составляет O (N). Вообще говоря, дни стрижки таким способом нетрудно определить и без компьютера.

Вот примерный вариант кода. Предполагается, что число N и массив цен уже введены пользователем в некоторые переменные. В третьем параметре функция вернет признаки стрижки для каждого дня (true - в этот день стрижемся, false - не стрижемся; массиву должно быть предварительно выделено место под N элементов). Массив цен не должен содержать отрицательных значений:

cheburator, ты как проффессионал, который пишет

return ((int*)arg2)[1] - ((int*)arg1)[1];

можешь объяснить, мне, непроффессионалу, который пишет

return *(int *)((int)arg2+4) - *(int *)((int)arg1+4);

смысл кода:
Ведь days

это bool, т.е. он равен или 1, или 0. Внутри if-блока он всегда равен 1,
а LastDay первый раз равен -1, в остальных случаях равен 1.
Т.е. profit = 2*cost, где i это первый день, в которой неформал решил постричся,
а остальные дни НЕ УЧИТЫВАЮТСЯ. Правильнй код:

Свернуть исходник 

Код:

int profit = 0;
  int LastDay = 0;
  for (i=0; i<N; i++)
  {
    LastDay++;
    if (days)
    {
      profit +=  LastDay * cost ;
      LastDay = 0;
    }
  }

и прога, только с одним циклом

Свернуть исходник 

Код:

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <iostream.h>
#include <conio.h>

const int N = 10;
int cost[] = {10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
bool days[N];

int getMaximumProfit (const int n, const int *cost, bool *days)
{
  if(n==1)
  {
    *days = true;
    return *cost;
  }
  int LastCost  = cost[n-1];
  int DaysCnt = 1;
  int DayNdx  = n - 1;
  int profit  = 0;
  for (int i=n-2; i>=0; i--)
  {
    if (LastCost < cost)
    {
      profit += DaysCnt*LastCost;
      days[DayNdx] = true;
      DayNdx = i;
      LastCost = cost;
      DaysCnt = 1;
    }
    else
    {
      days = false;
      DaysCnt++;
    }
  }
  profit += DaysCnt*LastCost;
  days[DayNdx] = true;

  return profit;
}

void main()
{
  int h = getMaximumProfit (N, cost, days);
  cout << h << endl;
  for(int i=0;i<N;i++)
  cout << days << endl;
  getch();
}

[QUOTE=Мerlin]смысл кода:
Ведь days

это bool, т.е. он равен или 1, или 0. Внутри if-блока он всегда равен 1,
а LastDay первый раз равен -1, в остальных случаях равен 1.
Т.е. profit = 2*cost, где i это первый день, в которой неформал решил постричся,
а остальные дни НЕ УЧИТЫВАЮТСЯ.[/QUOTE]
Пардон, ошибся, я хотел написать

 

Код:

profit += (i - LastDay) * cost ;
      LastDay = i;

(т. е. LastDay - день предыдущей стрижки). А насчет твоего варианта, да, программа с одним циклом менее громоздка, чем с двумя. Мне важно было показать основу алгоритма.

[QUOTE=cheburator]Пардон, ошибся, я хотел написать

(т. е. LastDay - день предыдущей стрижки).[/QUOTE]Если LastDay инициализировать 0-м, вместо -1, тогда покатить.

[QUOTE=Мerlin]Если LastDay инициализировать 0-м, вместо -1, тогда покатить.[/QUOTE]
Обрати внимание на условия задачи. В начале 0-го дня у чувака уже есть сантиметр волос! Поэтому в случае, когда i-й день - самая первая стрижка, длина волос равна i-(-1) = i+1. Поэтому в самом начале LastDay инициализируется минус единицей. Одновременно это и признак того, что стрижек ещё не было.
И ещё. В твоей проге почему-то отдельно выделен случай одного-единственного дня (if (n==1)...). Зачем?

[QUOTE=cheburator]Обрати внимание на условия задачи. В начале 0-го дня у чувака уже есть сантиметр волос! Поэтому в случае, когда i-й день - самая первая стрижка, длина волос равна i-(-1) = i+1. Поэтому в самом начале LastDay инициализируется минус единицей. Одновременно это и признак того, что стрижек ещё не было.[/QUOTE]Storno. Я не учел, что нумерация дней начинается с 0, а не с 1-ы.

Это дело вкуса. Можно и без того блока, но если вырожденный случай, imho, можно ограничиться 2-я командами.