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

Những tháng ngày vất vả

Tôi cứ nghĩ cuộc sống là đơn giản, nhưng tôi đã lầm. Cuộc sống quá phức tạp.
Trong thời gian qua, tôi luôn có những sự cố đến với mình và tôi cảm thấy rằng cuộc đời sao mà bất công với tôi