Задание
Телеканал XYZ разрабатывает новое игровое шоу, в котором участники должны сделать некоторый выбор чтобы получить приз. Игра состоит из треугольного стека шаров, на каждом из которых записано целочисленное значение, как показано ниже на примере.
Участник должен выбрать набор шаров, и его призом будет сумма чисел на них. Участник может взять шар, только если он берет все шары, находящиеся непосредственно над ним. Это может потребовать снятия дополнительных шаров по описанному правилу. Участник может не взять ни одного шара, в таком случае его приз будет равным нулю.
Директор телешоу заинтересован в том, чтобы участник получил максимальный приз для заданного стека. Так как он является Вашим босом, то попросил Вас решить эту задачу.
Входные данные
Каждый тест задается в нескольких строках. Первая строка содержит количество рядов [latex]N (1 ≤ N ≤ 1000)[/latex] в стеке. [latex]i[/latex]-ая из следующих [latex]N [/latex] строксодержит [latex]i[/latex] целых чисел [latex]B_{ij} (-10^{5}≤ B_{ij}≤ 10^{5}[/latex] для [latex]1 ≤ j ≤ i ≤ N)[/latex]; значение [latex]B_{ij}[/latex] равно числу, записанному на [latex]j[/latex]-ом шаре в [latex]i[/latex]-ом ряду стека (первый ряд — самый верхний, в каждом ряду первым шаром является самый левый).
За последним тестом следует строка, содержащая один ноль.
Выходные данные
Для каждого теста вывести в отдельной строке целое число — максимальный приз, который может получить участник игры для заданного стека шаров.
Тесты
| Ввод | Вывод |
| 4 3 -5 3 -8 2 -8 3 9 -2 7 2 -2 1 -10 3 1 -5 3 6 -4 1 0 |
7 0 6 |
| 3 7 2 1 3 4 6 2 5 9 2 1 2 0 |
23 16 2 |
Код
|
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 31 32 33 34 35 36 37 38 39 40 41 42 43 44 |
import java.util.*; import java.lang.*; import java.io.*; public class Main { public static void main (String[] args) { Scanner in = new Scanner(System.in); int[][] s = new int[1001][1001]; while (in.hasNextInt()) { int n = in.nextInt(); int ans = 0; if(n==0) { break; } else { for (int i = 1; i <= n; i++) { for (int j = 1; j <= i; j++) { s[i][j] = in.nextInt(); s[i][j] += s[i - 1][j]; } } for (int j = 1; j <= n; j++) { for (int i = j; i <= n; i++) { s[i][j] += s[i - 1][j - 1]; } for (int i = n - 1; i >= j; i--) { s[i][j] = Math.max(s[i][j], s[i + 1][j]); } } for (int i = 1; i <= n; i++) { ans = Math.max(ans, s[i][i]); } System.out.println(ans); } } } } |
Решение
Иницианилизируем двумерный массив [latex]s[/latex], который будет играть роль нашего стека. При считывании массива будем сразу суммировать предыдущие шары. Далее будем хранить в нижних шарах стека сумму всех верхних и при обходе с помощью максимума находить оптимальный путь. Остаётся только найти максимум среди получившихся сумм. Это и будет нашим ответом.
— Вы помните, что у нас формулы должны быть в ТЕХ?