FC
можно написать функцию перехода в состояние n
Size: a a a
2018 June 14
АУ
Это перебором получается решение, так?
это называется динамическое программирование. Там не полный перебор будет, O(n*k), где n недель и k - максимум надо рабочих
АУ
Оптимальная стоимость найма k рабочих на n-й неделе:
F(n, k) = min (F(n-1, k-m) + D(m)),
где m - разница в количестве рабочих, может быть отрицательной, аккуратно надо. n - номер недели. k - количество рабочих, D(m) - стоимость найма разницы. И не надо брать клетки, где рабочих меньше, чем запрос на текущую неделю.
F(n, k) = min (F(n-1, k-m) + D(m)),
где m - разница в количестве рабочих, может быть отрицательной, аккуратно надо. n - номер недели. k - количество рабочих, D(m) - стоимость найма разницы. И не надо брать клетки, где рабочих меньше, чем запрос на текущую неделю.
АУ
может быть, можно и проще, но это кажется сработает, только аккуратно написать
NM
Блин, это просто
NM
Но я не могу мысль уловить :D
АУ
Но я не могу мысль уловить :D
Сорри, у меня какое-то математическое костноязычие развилось
NM
Типа такого?
NM
Сорри, у меня какое-то математическое костноязычие развилось
Не, я прост не очень умный
FC
но ведь в случае, если мы нанимаем - мы платим 400 долларов сверху
FC
а если увольняем - только содержание оставшимся
АУ
Типа такого?
Да, только мне трудно на ночь глядя числа проверять. Смысл в том, что нанять лишнего заранее может оказаться выгоднее. Поэтому ты для каждой следующей недели берешь возможные количества нанятых и пробуешь нанять ещё или уволить. И смотришь минимум
FC
формулы получаются сильно разные
NM
Да, только мне трудно на ночь глядя числа проверять. Смысл в том, что нанять лишнего заранее может оказаться выгоднее. Поэтому ты для каждой следующей недели берешь возможные количества нанятых и пробуешь нанять ещё или уволить. И смотришь минимум
Ну да, эту фишку я понял
NM
Или уволить не всех
FC
то есть для найма
400 + (n*200)
NM
то есть для найма
400 + (n*200)
Ну я примерно так и считаю
NM
По условию нихрена не понятно
АУ
а если увольняем - только содержание оставшимся
Вот поэтому чтобы получить 5 на какой-то неделе, надо выбрать, что выгоднее, нанять три на прошлой и потом ещё два, или нанять семь на прошлой, а потом остальных на мороз