Найти минимальные суммарные затраты на обед

Question

Помогите решить задачу пожалуйста:

Даня в обеденный перерыв ходит в одно и то же кафе. Ему, как сотруднику банка, положено специальное предложение: при каждой покупке больше, чем на 100 рублей, Даня получает купон на бесплатный обед.

Даня узнал стоимость своих обедов на ближайшие n дней. Ему хочется минимизировать свои затраты, грамотно используя талоны. Требуется найти минимальные суммарные затраты Дани на обеды.

Формат входных данных

В первой строке дается натуральное число n(0≤n≤100). В каждой из n строк записана стоимость обеда в каждой из дней (неотрицательное целое число, не больше, чем 300).

Формат выходных данных

В первой строке выдайте минимально возможную суммарную стоимость обедов.

Замечание

В первом примере Дане придется купить первые 3 обеда, после чего у него появится талон. Этот талон будет выгоднее всего потратить на последний обед. Таким образом, он купит первые 4 обеда и получит пятый бесплатный.

int days = int.Parse(Console.ReadLine()!);

if (days < 0 || days > 100) throw new ArgumentOutOfRangeException(
   $"Argument {days} is Out Of Range Exception. Argument must be between 0 and 100.");

var prices = new int[days];
var remainder = new List<int>();
var coupons = 0;

for (int i = 0; i < days; i++)
{
    var price = int.Parse(Console.ReadLine()!);

    if (price < 0 || price > 300) throw new ArgumentOutOfRangeException(
        $"Argument {price} is Out Of Range Exception. Argument must be between 0 and 300.");

    if (coupons != 0) remainder.Add(price); // Запоминаем дни на которые можем потратить первый купон
    coupons += price > 100 && coupons == 0 ? 1 : 0; //Находим первый купон
    prices[i] = price;
}

var maxDiscount = 0;

while (coupons != 0 && remainder.Sum() != 0)
{
    var temp = remainder.Max(); // находим день с максимальной ценой чтоб потратить купон
    maxDiscount += temp;
    remainder.Remove(temp); 
    coupons--;
    //смотрим можем ли найти новый купон
    for (var i = 0; i < remainder.Count - 1; i++)
    {
        if (remainder[i] > 100)
        {
            remainder.Remove(remainder[i]);
            coupons++;
            break;
        }
     }
 }
 // Выводим на экран максимально возможную низкую сумму
 Console.WriteLine(prices.Sum() - maxDiscount);

Код который написал проходит не все тесты к сожалению тесты не доступны к просмотру. Я вообще не понимаю что ещё я мог упустить. Помогите пожалуйста.

Answer 1

    static void Main(string[] args)
    {
        int days = int.Parse(Console.ReadLine()!);

            if (days < 0 || days > 100) throw new ArgumentOutOfRangeException(
                    $"Argument {days} is out of range. Argument must be between 0 and 100.");

            int min = 0;
            var max = days * 300;
            var prices = new int[days + 1];

            for (int i = 1; i <= days; i++)
            {
                var price = int.Parse(Console.ReadLine()!);

                if (price < 0 || price > 300) throw new ArgumentOutOfRangeException(
                    $"Argument {price} is out of range. Argument must be between 1 and 300.");

                prices[i] = price;
            }

            var dp = new int[days + 1, days + 2];
           
            for (int i = 0; i <= days; i++)
            {
                for (int j = 0; j <= days + 1; j++)
                {
                    dp[i, j] = -1;
                }
            }

            for (int i = 0; i < days; i++)
            {
                if (max >= GetMinimumSum(days, i, prices, dp, max))
                {
                    min = GetMinimumSum(days, i, prices, dp, max);
                    max = min;
                }
            }

            Console.WriteLine(min);
    }
    
    static int GetMinimumSum(int i, int j, int[] prices, int[,] dp, int max)
    {
        if (j > i) return max;
        else
        {
            int min;
            int price = prices[i];

            if (j <= 0)
            {
                if (i > 0)
                {
                    if (price > 100)
                    {
                        return GetMinimumSum(i - 1, j + 1, prices, dp, max);
                    }
                    else
                    {
                        min = Math.Min(GetMinimumSum(i - 1, j + 1, prices, dp, max), GetMinimumSum(i - 1, j, prices, dp, max) + price);
                    }
                }
                else return 0;
            }
            else
            {
                if (dp[i, j] != -1) return dp[i,j];

                if (price > 100)
                {
                    min = Math.Min(GetMinimumSum(i - 1, j + 1, prices, dp, max), GetMinimumSum(i - 1, j - 1, prices, dp, max) + price);
                }
                else
                {
                    min = Math.Min(GetMinimumSum(i - 1, j + 1, prices, dp, max), GetMinimumSum(i - 1, j, prices, dp, max) + price);
                }
            }

            dp[i, j] = min;
            return min;
        }
    }

Решение на основе помощи ответа @Harry

Answer 2

Я тоже долго мучился с этой задачей. В приведенном выше решении используется большое количество рекурсивных вызовов, которые, насколько я знаю, имеют накладные расходы. Я решил эту задачу так:

public static int Task9_v3(int[] dinnerCosts)
        {
            // dp[i, j] - минимальная сумма для рассмотренных i чисел, при условии, что у нас еще осталось j купонов
            int[,] dp = new int[dinnerCosts.Length + 1, dinnerCosts.Length + 2];
            // Заполняем таблицу дп большими значениями, т.к мы ищем минимум
            for (int i = 0; i < dp.GetLength(0); i++)
                for (int j = 0; j < dp.GetLength(1); j++)
                    dp[i, j] = 100 * 300 + 1;
            // База дп
            dp[0, 0] = 0;
            // Идем по всем числам
            for (int i = 1; i < dp.GetLength(0); i++)
            {
                // Идем по всем возможным занчениям оставшихся купонов
                // Если мы рассмотрели i чисел, у нас не может быть j > i,
                // т.е если рассмотрели, например, 5 чисел у нас не может быть 6 неиспользованных купонов 
                for (int j = 0; j <= i; j++)
                {
                    dp[i, j] = Math.Min(dp[i, j], dp[i - 1, j] + dinnerCosts[i - 1]);
                    if (dinnerCosts[i - 1] > 100)
                        dp[i, j + 1] = Math.Min(dp[i, j + 1], dp[i - 1, j] + dinnerCosts[i - 1]);
                    if (j >= 1)
                        dp[i, j - 1] = Math.Min(dp[i, j - 1], dp[i - 1, j]);
                }
            }
            int result = int.MaxValue;
            for (int j = 0; j <= dinnerCosts.Length; j++)
                result = Math.Min(result, dp[dinnerCosts.Length, j]);
            return result;
        }

Вот дополнительные источники, которые я нашел, с разбором этой задачи: https://www.youtube.com/watch?v=jdqXyG14-3k&ab_channel=%D0%A8%D0%B0%D1%85%D0%B7%D0%BE%D0%B4%D0%A2%D0%BE%D1%88%D0%BF%D1%83%D0%BB%D0%B0%D1%82%D0%BE%D0%B2 - где то на 02:06 начинается решение этой задачи.

https://inf.1sept.ru/article.php?ID=200601603 - тоже есть эта задача

БЛОГ НА HUSL

Найти минимальные суммарные затраты на обед

Ответы (2 шт):