Đường đi dài nhất

[laurent]

Cho mảng a[i,j] như ví dụ,tìm đường đi dài nhất từ ô [1,1] tới hàng cuối cùng.
Với bài này ta có thể dùng phương pháp quy hoạch động với mảng quy hoạch động là mảng hai chiều, tuy nhiên yêu cầu: xây dựng mảng quy hoạch động là mảng một chiều.
VD:
input
4 --> số n
7
3 8
4 2 1
8 6 7 3
output
24 --> tổng đường đi
7 -> 8 -> 2 -> 7

[bld]

ví dụ khó hiểu quá
nếu bạn gõ có nhiều dấu cách thì đặt vô giữa [code và [/code] cho dễ đọc

[Master_Baby]

vậy biến mảng 2 chiều thành mảng một chiều cái này cũng đơn giản muh
Ô quy hoạch động tương ứng với hàng i, cột j:

a[i, j] <=> b[i * n + j]
k = i * n + j

Như vậy truy vết cũng dễ dàng hơn nhiều: c[k] = đỉnh cha của k.

[huysun]

   7
  8 3
 4 2 1
3 4 7 3

từ ô a[i,j] chỉ được đi đến ô a[i+1,j]hoặc ô a[i+1,j+1]
đường đi được nhiều điểm nhất:
a[1,1]=7 -> a[2,1]=8 -> a[3,2]=2 -> a[4,3]=7 (tổng là 24)

thuật toán:
chon mảng b với b[1,1]=a[1,1]; b[i,j]là điểm cao nhất có thể khi ở ô [i,j]
hay b[i,j]=max(b[i-1,j] , b[i-1,j-1]) +a[i,j].

[laurent]

Mình thấy bạn Huysun có thuật toán đúng rồi, ví dụ cũng đúng đề luôn nhưng còn mảng một chiều bạn có ý kiến không? Mình cảm ơn bạn b|d vì góp ý. Bạn Master_baby dùng hai mảng b và c phải hông dạ?

[lulumi03]

sao quởn vậy, pót lên làm gì làm người khác đau dầu9 wa1 cha nội

[laurent]

Ơ, tui đang tìm sự giúp đỡ mà, bạn có cách nào không đóng góp giùm tui đi, cảm ơn nha

[bld]

thuật toán của huysun :
thêm b[1,1] := a [1,1]
về mảng 1 chiều:
dùng mảng b như mảng 1 chiều với b[i,j] tương ứng với b[sum(1..i-1)+j]
cái này tiết kiệm bộ nhớ hơn của Master_BaBy nhưng việc truy xuất khó khăn hơn ,
tóm lại mong mọi người đóng góp ý kiến chỗ mảng 1 chiều

[laurent]

Tui mới nhận ra là cách của bạn Master_baby là đổi từ mảng hai chiều sang mảng một chiều, nhưng cách đổi đó là dùng cho ma trận vuông, còn ở đây là ma trận tam giác dưới mà, bạn còn cách nào khác hông?

[bld]

thực ra cách của MB vẫn dc chứ , linh động một chút , thì làm cũng ra
có 1 cách dùng mảng 1 chiều vẫn ngon ăn : đó là mảng 1 chiều kiểu record ( ) lưu tọa độ [i,j]
còn đây là cách suy nghĩ của mình :
gọi n là độ dài đáy ma trận tam giác A :
=> số phần tử của ma trận = n*(n+1)/2
lập bảng phương án B[1..n*(n+1)/2] ,k là số thứ tự của 1 phần tử trong mảng đó
và xây dựng hàm G(k,i hoặc j) để xác định tọa độ [i,j] của phần tử thứ k trong mảng A và thủ tục H(i,j) đổi tọa độ [i,j] thành số thứ tự K (trong n*(n+1)/2) phần tử )
với B[1]=A[1,1] ; B[k]=Max(B[H(G(k,i)-1,G(k,j)),H(G(k,i)-1,G[k,j]-1));
quá rắc rối (và khó hiểu) đúng không
vì vậy mong mọi người cùng đóng góp để có cách giải hay nhất