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

Турниры > CEN303 2013-15 Questions > задача:


50842 - Minimum Sum Triangle - DP

CEN303 2013-15 Questions

Старт: 15.дек.2013 в 14:00:00
Финиш: 15.дек.2013 в 19:00:00
Турнир завершён!
• Турнирная таблица

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

Задачи турнира

• 50472 - Minimum Sum Triangle
• 50842 - Minimum Sum Triangle -...
• 50319 - Toll Plazas
• 51000 - Book Index
• 50531 - File Decryption
• 50464 - From Tirana to Durres
• 13-Fall2-10. 50411 - Sum of the Lea...
• 13-Fall2-20. 50687 - Pascal Triangle - 2
• 13-Fall2-40. 50753 - Average of the...
• 13-Fall2-50. 50686 - The Container

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

Если у вас есть предложения или пожелания по работе 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