Алгоритм определения максимального удовольствия

Саму проблему можно найти здесь . Суть в том, что Бесси катается на американских горках, но у нее кружится голова. Каково максимальное количество удовольствия, которое она может получить, не превысив «предел головокружения». Входные данные состоят из:

« NKL

где N (1 ≤ N ≤ 1000) - это количество секций в этой конкретной американской горке; K (1 ≤ K ≤ 500) - это количество, которое Бесси уровень головокружения снизится, если она будет держать глаза закрытыми на любом участке поездки; а L (1 ≤ L ≤ 300 000) - это предел головокружения, который может терпеть Бесси - если ее головокружение когда-либо станет больше, чем L, Бесси заболеет , и это не весело!

В каждой из следующих N строк будет два целых числа:

FD

где F (1 ≤ F ≤ 20) - это увеличение общего веселья Бесси, которое получит оболочка, если она оставит ее глаза открыты на этом разделе, и D (1 ≤ D ≤ 500) - это увеличение ее уровня головокружения, если она будет держать глаза открытыми на этом разделе. Разделы будут перечислены по порядку ».

Мой алгоритм решения этой проблемы выглядит вот так:

        cin >> N; // sections
        cin >> K; // amount dizziness can go down
        cin >> L; // dizzy ceiling
        belowL = L; // sets the amount of dizzy left

        for (int i = 0; i < N; i++) {
            cout << "\n" << i;
            cin >> F >> D; // fun increase and dizzy increase
            if (D < belowL) {
                if (F >= D) {
                    funTotal += F;
                }
            }
            else {
                belowL -= K;
            }

Однако это не всегда дает правильный результат. В чем проблема? Он должен выбрать забавный вариант, если только он не поставит Бесси выше порога болезни.Есть ли лучший способ сделать это?

17
задан Linell 15 February 2012 в 20:20
поделиться

1 ответ

Он должен выбрать забавный вариант, если только он не поставит Бесси за порог болезни. Есть ли лучший способ сделать это?

Проблема в том, что вы не максимально развлекаете здесь, вы просто мешаете Бесси заболеть. Когда вы доберетесь до секции, которая поставит ее выше предела головокружения, вы сможете добавить больше удовольствия, вернувшись назад и выбрав вариант «невесело» в предыдущем разделе. Скажем, у вас есть ввод, как это, в порядке F D:

1 400
5 450
10 25
18 75
20 400

Далее, скажем, что она уже близка к головокружительному пределу, когда она достигает первого раздела выше. Вы можете выбрать забавный вариант в первых двух разделах и получить увеличение F на 6 и увеличение D на 850. Возможно, это ставит ее прямо на пределе. Теперь у вас нет выбора, кроме как выбрать вариант «невесело» для последующих разделов. С другой стороны, если вы выберете опцию «невесело» для первых двух разделов, вы можете выбрать опцию «Забавно» для следующих трех и получить увеличение F на 48 при увеличении D всего на 500.

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

5
ответ дан 30 November 2019 в 14:24
поделиться
Другие вопросы по тегам:

Похожие вопросы: