Саму проблему можно найти здесь . Суть в том, что Бесси катается на американских горках, но у нее кружится голова. Каково максимальное количество удовольствия, которое она может получить, не превысив «предел головокружения». Входные данные состоят из:
« 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;
}
Однако это не всегда дает правильный результат. В чем проблема? Он должен выбрать забавный вариант, если только он не поставит Бесси выше порога болезни.Есть ли лучший способ сделать это?
Он должен выбрать забавный вариант, если только он не поставит Бесси за порог болезни. Есть ли лучший способ сделать это?
Проблема в том, что вы не максимально развлекаете здесь, вы просто мешаете Бесси заболеть. Когда вы доберетесь до секции, которая поставит ее выше предела головокружения, вы сможете добавить больше удовольствия, вернувшись назад и выбрав вариант «невесело» в предыдущем разделе. Скажем, у вас есть ввод, как это, в порядке F D:
1 400
5 450
10 25
18 75
20 400
Далее, скажем, что она уже близка к головокружительному пределу, когда она достигает первого раздела выше. Вы можете выбрать забавный вариант в первых двух разделах и получить увеличение F на 6 и увеличение D на 850. Возможно, это ставит ее прямо на пределе. Теперь у вас нет выбора, кроме как выбрать вариант «невесело» для последующих разделов. С другой стороны, если вы выберете опцию «невесело» для первых двух разделов, вы можете выбрать опцию «Забавно» для следующих трех и получить увеличение F на 48 при увеличении D всего на 500.
Ваш текущий алгоритм выбирает забавную опцию, если отношение F: D больше 1, и у вас осталось достаточно головокружения. Это разумно, но не оптимально. Вероятно, что никакое фиксированное соотношение не даст оптимального решения. Вместо этого вам необходимо учитывать преимущества и стоимость каждого варианта для каждого раздела.