BCTEST15 - Quân mã

Link Sub: http://www.spoj.com/PTIT/problems/BCTEST15/
Người Gửi: Dương Lee

• Problem:

Trên bàn cờ kích thước  ô, gồm m dòng, n cột. Các dòng được đánh số từ 1..m, từ trên xuống dưới, các cột được đánh số từ 1..n từ trái qua phải, mỗi ô ghi một số nguyên dương. Một quân mã đứng trên một ô của dòng 1 cần phải nhảy đến một ô nào đó của dòng m theo quy tắc đi của quân mã trên bàn cờ Quốc tế và chỉ được nhảy từ dòng có chỉ số bé đến dòng có chỉ số lớn hơn.  
Quy tắc đi quân mã trên bàn cở quốc tế: Từ ô có hình quân mã, nó có thể nhảy tới các ô có chấm đỏ.

Yêu cầu: Tìm cách nhảy sao cho tổng các số ghi trên các ô mà quân mã nhảy qua là lớn nhất (kể cả ô đầu tiên mà quân mã đứng).
Input
-          Dòng đầu ghi 2 số m, n (1≤m,n≤100) cách nhau bởi dấu cách.  
-          m dòng sau mỗi dòng ghi n số nguyên dương không quá 10000, các số cách nhau 1 dấu cách.

Output
Một số duy nhất là tổng lớn nhất của các số ghi trên các ô mà quân mã nhảy qua.

Example:

Input

3 5
9 4 5 6 7
3 6 8 9 1
9 6 2 8 3

Output:

26

• Solution:

Giải thích: Quân mã đi theo các ô có số được gạch chân. 9 -> 8-> 9.
Ý tưởng: sumM[i][j] = max (chess[i][j], chess[i][j]+max(sumM[i-2][j-1], sumM[i-1][j-2], ... )); Vì quân mã chỉ đi từ hàng chị số thấp đến cao vậy nên ta có thể duyệt xuôi và lưu lại giá trị max có thể có của nó. Dễ hiểu là: Tại mỗi vị trí thì max tại đó sẽ là max của bước cha + chính nó. VD: chess[3][5]: 9 4 5 6 7 3 6 8 9 1 9 6 2 8 3 -> sumM[3][5]: 9 4 5 6 7 8 12 17 13 26 23 15 20 20 -> Max: 26

• Code:

C++:

JAVA:

Author : DL

Share this

Related Posts