Олимпиадные задачи по программированию. Ч. 3. Лучшие решения. Ускова О.Ф - 25 стр.

UptoLike

ВУЗ: 

ВГУ | Воронеж

Составители: 

Рубрика: 

25
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
- Каждый шаг на пути может осуществляться вниз по
диагонали влево или вниз по диагонали вправо.
- Число строк в треугольнике >1 и <=100.
- Треугольник составлен из целых чисел от 0 до 99.
Формат входных данных: первым числом во входном файле с
именем input.txt является количество строк в треугольнике.
Формат выходных данных: в выходной файл с именем output.txt
записывается только наибольшая сумма в виде целого числа .
Пример
входные данные выходные данные
5 30
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
РЕШЕНИЕ
Это типичная задача на метод динамического
программирования. Пусть А[i,j] означает j-ое число в i-ой
строке треугольника, а S[i,j]- наибольшую сумму чисел на пути
от вершины треугольника до этого числа . Очевидны
соотношения:
S[1,1] = A[1,1]
S[i,j] = max(S[i-1, j], S[i-1,j-1]) + A[i,j] (1<=j<=I<=N, i>1)

Страницы