ГлавнаяСборникиТурнирыРазделыФорумыУчастникиПечатьПомощьО системе

Сборники > Data Structures > задача:


50842 - Minimum Sum Triangle - DP

Гость
• Вопросы к жюри (1)

Задачи сборника

• 50771 - BST Level Sum
• 50773 - Balanced Sum Tree
• 50536 - Epoka Furgon Shpk
• 50506 - The Biggest Island
• 50682 - Hotel Durres
• 50777 - Dwarfs Maze
• 50488 - Connecting Wires
• 50472 - Minimum Sum Triangle
• 50842 - Minimum Sum Triangle -...
• 50781 - ReversesreveR
• 50676 - Cinema Millennium
• 50780 - Hot Potato - Revisited
• 50678 - The Jumping Rabbit
• 50793 - Top M Customers
• 51073 - Campus Tours for High Sch...
• Check-Mate
• Post Office Delivery

Обратная связь

Если у вас есть предложения или пожелания по работе Contester, посетите форум сайта www.contester.ru.

Лимит времени 2000/4000/4000/4000 мс. Лимит памяти 65000/65000/65000/65000 Кб.
Adapted from USACO by Ibrahim Mesecan.

Minimum Sum Triangle - DP

Consider the number triangle shown on the right. Write a program that calculates the smallest sum of numbers that can be passed on a route that starts at the top and ends somewhere on the base. Similar to Pascal Triangle, each step can go either diagonally down to the left or diagonally down to the right.

Question:
Write a program that finds the smallest sum that starts at the top and ends somewhere at the base.

Input specification
The first line contains an integer (n) which represents the number of rows. Then, in the following n lines, you will be given numbers which are between 0 and 1000. The numbers are given such that

  • the first line will have one number
  • the second line will have two numbers
  • : : :
  • the nth line will have n numbers
where 1 ≤ n ≤ 250.

Output specification
A single line containing the smallest sum using the traversal specified.

Sample Input I   
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
Sample Output I   
17


Для отправки решений необходимо выполнить вход.

www.contester.ru