Đường đi lớn nhất trong tam giác số
Xem dạng PDF
Gửi bài giải
Điểm:
1,00 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
256M
Input:
stdin
Output:
stdout
Dạng bài
Cho một tam giác số gồm n hàng. Mỗi phần tử trong hàng (trừ hàng cuối) có thể đi xuống hàng kế tiếp, theo một trong hai hướng:
Từ trên xuống (cùng chỉ số cột j), hoặc
Từ trên bên trái xuống (chỉ số cột j - 1).
Hãy tìm tổng lớn nhất có thể đạt được khi đi từ đỉnh tam giác xuống đáy.
Dữ liệu vào (Input)
Dòng đầu tiên chứa số nguyên n (1 ≤ n ≤ 100).
Tiếp theo là n dòng, dòng thứ i chứa i số nguyên là các phần tử của hàng thứ i. (Các số có giá trị tuyệt đối ≤ 10⁴)
Dữ liệu ra (Output)
In ra một số nguyên — là tổng lớn nhất có thể đạt được.
Ví dụ 1
Input
4
2
4 1
1 2 7
8 3 9 6
Output
19
Giải thích:
Đường đi lớn nhất là: 2 → 4 → 2 → 9 = 19
Bình luận
wow