Con kiến

Con kiến

Có một ống hình trụ, khi trải phẳng ra có thể là một bảng MxN ô. Giá trị A[i,j] là lượng thức ăn có ở ô ở dòng i cột j. Một con kiến xuất phát từ một ô ở mép bên trái của hình trụ và bò sang mép bên phải. Từ ô (i,j) kiến có thể bò sang 1 trong 3 ô (i–1,j+1), (i,j+1) hoặc (i+1,j+1).( Chú ý: vì ống hình trụ nên kiến đang ở dòng 1 có thể bò xuống dòng M và ngược lại). Bò qua ô nào thì kiến mang theo toàn bộ lượng thức ăn ở ô đó. Hãy tìm đường đi mà kiến kiếm được nhiều thức ăn nhất.

Hướng dẫn: Để xử lí tình huống hình trụ, ta lưu dòng 0 là dòng M và dòng M+1 là dòng 1.Khi đó tương tự như bài toán ban đầu, gọi F(i,j) là lượng thức ăn kiến có được khi bò đến ô (i,j), ta thiết lập được công thức QHĐ sau:
• F(i,1)=A[i,1]
• F(i,j)=max(F(i–1,j–1),F(i,j–1),F(i+1,j+1))+A[i,j] với j>1