Nộp bài
Điểm:
900 (thành phần)
Thời gian:
1.0s
Bộ nhớ:
256M
Input:
bàn phím
Output:
màn hình
Tác giả:
Dạng bài
Bạn được cho một ma trận tam giác bậc n. Cụ thể là ma trận sẽ có định dạng như sau:
a_{1,1}
a_{2,1}\ a_{2,2}
a_{3,1}\ a_{3,2}\ a_{3,3}
\dots
a_{n,1}\ a_{n,2}\ a_{n,3}\dots a_{n,n}
Tại ô (i,j) sẽ có giá trị là a_{i,j}. Bạn bắt đầu xuất phát từ đỉnh (1,1). Mỗi lượt bạn có thể di chuyển đến ô (i+1,j) hoặc ô (i+1,j+1). Nhiệm vụ của bạn là tìm một đường đi từ ô xuất phát đến đích là bất cứ ô nào ở hàng n sao cho tổng giá trị của tất cả các ô trên đường đi (tính cả ô xuất phát và kết thúc) là lớn nhất có thể
Input, Output và Subtasks
Input
- Dòng đầu tiên gồm một số nguyên dương n là bậc của ma trận (1\le n\le 1000)
- Sau đó là n dòng, dòng thứ i bao gồm i giá trị a_{i,1},a_{i,2},\dots,a_{i,i} (|a_{i,j}|\le 100). Các giá trị nhập vào được cách nhau bởi một dấu khoảng trắng
Output
- Một dòng duy nhất ghi kết quả của bài toán.
Sample
Input
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
Output
30
Note
Đường đi tối ưu: (1,1)\rightarrow (2,1)\rightarrow (3,1)\rightarrow (4,2)\rightarrow (5,2). Tổng là 7+3+8+7+5=30
Bình luận