Phương pháp: Quy hoạch động.

Tổ chức dữ liệu:

• ~V[x]~: độ cao tại vị trí ~x~;
• ~F[k,x]~: thời gian nhỏ nhất xét đến vị trí ~x~, đã xây ~k~ đường hầm hoặc cầu cạn;
• ~Right[x]~ vị trí đầu tiên bên phải vị trí ~x~ có độ cao bằng với độ cao tại vị trí ~x~.
• ~H[i]~: vị trí có độ cao ~i \to H[V[x]]=x~;

Thuật toán:

Tính trước ~Right[x]~:

for( int x = 0; x <= N; ++x ) { 
      if( x > 0 && V[x] != V[x-1] && H[V[x]] != -1 )
         Right[H[[x]]] = x;
      H[V[x]] = x;
   }

Lấy ~F[k][x]~ tối ưu các giá trị sau:

• ~F[k, x+1] = min(F[k,x+1], F[k,x]+ A, F[k,x]+ B)~, trường hợp không xây thêm đường hầm hoặc cầu cạn.
• ~F[k+1, Right[x]] = min(F[k+1, Right[x]], F[k][x] + C*(Right[x]-x))~, trường hợp xây dựng thêm đường hầm hoặc cầu cạn bắt đầu tại vị trí ~x~ và kết thúc tại vị trí ~Right[x]~.

Kết quả là: ~min(F[k,N])~, với ~k = 1...K~.