1976. Number of Ways to Arrive at Destination

Tóm tắt đề bài

Cho một đồ thị vô hướng. Giả sử

$x$ là độ dài đường đi ngắn nhất từ điểm

$0$ đến điểm

$n-1$.

Đếm số đường đi có khoảng cách đúng bằng

$x$

Tóm tắt lời giải

Giả sử, ta đã tính ra được

$x$.

Khi đó, ta xác nhận được với mỗi đỉnh

$u$ trong đồ thị, độ dài đường đi ngắn nhất từ

$0$ tới nó là

$f[u]$.

Quan sát: Nếu một con đường trong đồ thị mà đi từ

$u$ đến

$v$, có độ dài

$w$, mà thuộc một đường đi ngắn nhất nào đó, nó phải thỏa mãn:

$f[u]+w=f[v]$.

Vì thế, với mỗi đường đi trên đồ thị, ta có thể xác định được hướng đi của nó trong đường đi tối ưu, hoặc không xét nó vào tập hợp các đường đi có thể có trên đồ thị có hướng.

Khi đó, hướng đi của từng con đường trên đồ thị sẽ tạo thành một DAG, và ta có thể quy hoạch động trên đó. Ta có thể thiết lập một công thức quy hoạch động như sau:

• $g[u]$ là số đường đi ngắn nhất từ đỉnh
  $0$ đến đỉnh
  $u$.

Phần còn lại các học viên tự giải.

2008. Maximum Earnings From Taxi

Tóm tắt đề bài

Hành trình uber của bạn qua

$n$ điểm, nằm lần lượt từ

$0$ đến

$n$ trong hành trình. Có

$m$ khách đặt bạn, muốn đi quãng đường từ

$s_i$ đến

$e_i$ (

$e_i>s_i$) và sẽ trả bạn mức phí bằng

$e_i-s_i+ti{p}_i$. Bạn sẽ chỉ có thể chở mỗi lúc một người, nhưng sau khi trả một khách tại điểm

$u$ nào đó, bạn có thể bắt khách tiếp ngay tại điểm đó luôn.

Hãy tối ưu hóa lợi nhuận của bạn.

Tóm tắt lời giải

Ta lưu ý:

$en{d}_i\le n\le {10}^5$.

Gọi

$f[u]$ là số tiền tối ưu có thể dành được sau khi taxi đến được điểm

$u$.

Với mỗi chuyến xe ứng với thông số

$[s,e,tip]$, ta cập nhật

$f[e]=max(f[e],f[s]+e-s+tip)$. Ban đầu, khi chưa cập nhật chuyến xe nào

$f[e]$ mặc định bằng

$f[e-1]$ (đi đoạn đường không có thu nhập).

$f[0]=0$.

Với cách cập nhật thế này, ta cần sắp xếp các chuyến xe theo chiều tăng dần của điểm kết thúc. Sau đó, với mỗi điểm

$u$ trên đoạn đường:

• Ta cập nhật nó bằng với
  $f[u-1]$.
• Tìm xem có các chuyến xe nào kết thúc tại điểm
  $u$ không, nếu có, với mỗi chuyến xe, ta cập nhật nó theo công thức đã nói trên.

2556. Disconnect Path in a Binary Matrix by at Most One Flip

Tóm tắt đề bài

Cho một quần đảo, địa thế của nó có thể được mô phỏng bởi một lưới vuông

$m\times n$. Các ô

$1$ trên quần đảo là đất liền, còn

$0$ trên quần đảo là nước. Hỏi, liệu ta có thể bỏ đi một ô đất liền nào đó (thay bằng nước), để "ngắt kết nối" giữa ô trên trái ngoài cùng, và ô dưới phải ngoài cùng được không?

Tóm tắt lời giải

Gọi số đường đi đến ô

$(u,v)$ từ ô trái trên là

$f[u][v]$, từ ô phải dưới là

$g[u][v]$.

Quan sát: số đường đi từ hai góc lưới vuông mà đi qua ô

$(u,v)$ là

$f[u][v]\times g[u][v]$.

Tổng số đường đi là

$g[0][0]$.

Nếu ta đã tính được các mảng

$f$ và

$g$, thì việc tìm ô nào đó thỏa mãn để có thể flip, ứng với việc tìm một ô

$(u,v)$ thỏa mãn

$f[u][v]\times g[u][v]=g[0][0]$, tương ứng với việc tất cả đường đi đều đi qua ô

$(u,v)$ này.