Задача с сайта e-olymp.com
Условие задачи
Как-то Корвину – принцу Амбера, по каким-то важным делам срочно понадобилось попасть в самую далекую тень, которую он только знал. Как всем известно, самый быстрый способ путешествия для принцев Амбера – это Лабиринт Амбера. Но у Корвина были настолько важные дела, что он не хотел тратить время на спуск в подземелье (именно там находится Амберский Лабиринт). Поэтому он решил воспользоваться Новым Лабиринтом, который нарисовал Дворкин. Но этот Лабиринт не так прост, как кажется…
Новый Лабиринт имеет вид последовательных ячеек, идущих друг за другом, пронумерованных от [latex]1[/latex] до [latex]N[/latex]. Из ячейки под номером [latex]i[/latex] можно попасть в ячейки под номерами [latex]i+2[/latex] (если [latex]i+2 ≤ N[/latex]) и [latex]i+3[/latex] (если [latex]i+3 ≤ N[/latex]). На каждой ячейке лежит какое-то количество золотых монет [latex]{ k }_{ i }[/latex]. Для того чтобы пройти лабиринт нужно, начиная ходить из-за границ лабиринта (с нулевой ячейки) продвигаться по выше описанным правилам, при этом подбирая все монетки на ячейках, на которых вы делаете промежуточные остановки. Конечная цель путешествия – попасть на ячейку с номером [latex]N[/latex]. Дальнейшее путешествие (в любое место Вселенной) возможно лишь тогда, когда достигнув ячейки с номером [latex]N[/latex], вы соберете максимально количество монеток. Напишите программу, которая поможет Корвину узнать, какое максимальное количество монеток можно собрать, проходя Новый Лабиринт Амбера.
Входные данные
В первой строке входного файла содержится натуральное число [latex]N (2 ≤ N ≤ 100000)[/latex], а во второй [latex]N[/latex] целых чисел, разделенных одним пробелом, [latex]{ k }_{ i }[/latex] – количество монеток, лежащих в ячейке с номером [latex]i[/latex] [latex](0 ≤ i ≤ 1000)[/latex].
Выходные данные
В выходной файл вывести одно целое число – максимальное количество монеток, которое можно собрать, проходя лабиринт.
Тесты
| № | Входные данные | Выходные данные |
| 1 | 5 1000 2 3 1 3 |
6 |
| 2 | 2 1 2 |
2 |
| 3 | 4 1 3 100 0 |
3 |
Решение с использованием цикла
Код программы
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
#include <iostream> using namespace std; int main() { int n, i; cin >> n; int *dp; dp = new int [n+1]; for(i = 1; i<=n; ++i){ cin >> dp[i]; } dp[0] = 0; dp[1] = 0; for(int i = 2; i<=n; ++i){ if(i - 3 >= 0) dp[i] = dp[i] + max(dp[i-2], dp[i-3]); } cout << dp[n]; return 0; } |
Засчитанное решение на e-olymp.com.
Описание
Для хранения количества монет в каждой ячейке лабиринта используем массив [latex]dp[/latex] длиной [latex]n+1[/latex] элементов. При этом каждой ячейке лабиринта соответствует ячейка массива с тем же индексом, а нулевой элемент массива понимаем как точку перед входом в лабиринт. В цикле считываем количество монет в каждой ячейке, после чего обнуляем значение нулевого элемента массива, поскольку ячейка, соответствующая ему, находится вне лабиринта, и первого, поскольку в ячейку, соответствующую ему, невозможно попасть никаким образом. Далее в цикле для каждой ячейки лабиринта находим, какое максимальное количество монет может быть у Корвина после её посещения. В ячейку с номером [latex]i[/latex] он может попасть или из ячейки с номером [latex]i-2[/latex], или из ячейки с номером [latex]i-3[/latex]. При этом он несёт с собой все собранные ранее монеты, и добавляет к ним те, что находятся в данной ячейке. Таким образом, формула для нахождения максимального количества монет после посещения [latex]i[/latex]-й ячейки имеет вид [latex]dp[i] = dp[i] + max(dp[i-2], dp[i-3])[/latex], и ответ к задаче хранится в [latex]n[/latex]-й ячейке массива. Дополнительно требуется проводить проверку на выход за границы массива.
Код на ideone.com.
Решение с использованием рекурсивной функции
Код программы
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 |
#include <iostream> using namespace std; int *dp; int *used; int f(int i){ if(i < 2) return 0; else{ if(used[i] == 0){ dp[i] = dp[i] + max(f(i-2), f(i-3)); used[i] = 1; } return dp[i]; } } int main() { int n, i; cin >> n; dp = new int [n+1]; used = new int [n+1]; for(i = 1; i<=n; ++i){ cin >> dp[i]; used[i] = 0; } f(n); cout << dp[n]; return 0; } |
Засчитанное решение на e-olymp.com.
Описание
В данном случае используется функция [latex]f[/latex], принимающая номер ячейки массива и возвращающая максимальное количество монет после посещения ячейки с этим номером. Сначала объявляются два глобальных массива:
[latex]dp[/latex], в [latex]i[/latex]-й ячейке которого изначально хранится количество монет в [latex]i[/latex]-й ячейке лабиринта, и [latex]used[/latex], элементы которого принимают значения [latex]0[/latex] или [latex]1[/latex] (значение [latex]0[/latex] в [latex]i[/latex]-й ячейке означает, что максимальное количество монет после посещения
ячейки лабиринта с тем же номером рассчитано ещё не было). Далее всё происходит как в решении с использованием цикла, но одновременно с чтением входных данных обнуляются элементы [latex]used[/latex], а вместо второго цикла происходит вызов функции [latex]f[/latex]. Сама же функция [latex]f[/latex], если значение параметра меньше двух, возвращает [latex]0[/latex], а иначе, если этого не было сделано ранее, вычисляет максимальное количество монет после посещения ячейки с номером [latex]i[/latex] по формуле [latex]dp[i] = dp[i] + max(dp[i-2], dp[i-3])[/latex] и возвращает его.
Код на ideone.com.
Кроме того, об идее решения данной задачи можно почитать здесь.
Молодец. Неплохо описано.
Вот только по первому решению есть замечания.
— Вы начинаете цикл с 2, потом проверяете и если меньше 3 то ничего не делаете. проще начать цикл с 3 и ничего не проверять.
— Вы обнуляете первую ячейку массива, т.к. по условию начинать можно только с нулевой. Логичнее поставить там отрицательное число монет. Тогда в первую ячейку оптимальный путь точно не зайдёт. Для данной задачи (определение не пути, а числа монет) это не важно, но…
Есть рекомендация различать математические формулы и фрагменты кода. Математическая формула может выглядеть, например, так — [latex]d_{i} = d_{i} + \max \left\{ d_{i-2}; d_{i-3} \right\},[/latex] а реализующий ее фрагмент кода может выглядеть так — dp[i] += max(dp[i-2], dp[i-3]),