Bài toán Quy hoạch động

 Baøi Taäp Qui hoaïch ñoäng

Baøi 1. Tam giaùc soá:

Cho tam giác số như hình vẽ. 

Ta định nghĩa một đường đi trong tam giác số là đường đi xuất phát từ hình thoi ở đỉnh tam giác và đi đến được các hình thoi có chung cạnh với nó, đường đi kết thúc khi gặp một hình thoi ở đáy tam giác.

Yêu cầu: Hãy tìm một đường đi trong tam giác số sao cho tổng giá trị của các ô trong đường đi có giá trị lớn nhất.

Dữ liệu vào: Cho trong file văn bản TRIANNUM.INP có cấu trúc như sau:

Dòng 1: Ghi số nguyên dương N là số hàng của tam giác (1 ≤ N ≤ 100).

Dòng thư i trong N dòng tiếp theo: Ghi i số nguyên dương lần lượt là giá trị của các ô trên dòng thứ i tưng ứng trong tam giác (Các số có giá trị không quá 32000). Các số được ghi cách nhau một dấu cách.

Dữ liệu ra: Ghi ra file văn bản TRIANNUM.OUT theo cấu trúc:

- Dòng 1: Ghi ra số nguyên dương S là tổng giá trị của đường đi tìm được.

-Doøng tieáp theo caùc soá treân ñöôøng ñi vaø caùch ñi (T) traùi , (P) phaûi.

Ví duï :

TRIANNUM.INP	TRIANNUM.OUT
5	30
7	7   T   3   T   8   P   7   T    5
3     8
8      1    0
2    7      4    4
4    5      2    6    5