Một giá đựng đồ dựng đứng hình chữ nhật chia thành ô gồm hàng đánh số từ dưới lên và cột đánh số từ trái sang phải, . Mỗi khi cần lấy đồ đạc tại một ô (hàng , cột ) nào đó, người ta phải dùng một cái thang dựng đứng theo cột để leo lên, trong quá trình leo, có thể lấy đồ đạc tại các ô trên cột và hai cột kề bên cột với điều kiện các ô đó không cao hơn ô tại vị trí leo lên tại cột .
Ta cần lấy đồ vật tại một số ô, hãy chọn một số cột đặt thang sao cho hai yêu cầu sau được thoả mãn:
Lấy được mọi đồ vật cần lấy:
Tổng các chiều cao thang cần leo là nhỏ nhất (mỗi lần đặt thang tại một cột, chiều cao thang được tính bằng chỉ số ô cao nhất cần leo lên tại cột đó).
Dữ liệu:
Dòng thứ nhất ghi hai số nguyên dương ;
Dòng thứ hai ghi số nguyên dương là số ô cần lấy đồ tại đó;
Trong dòng tiếp theo, mỗi dòng ghi hai số có nghĩa là cần lấy đồ ở ô tại cột dòng .
Kết quả:
Ghi ra một số duy nhất là tổng chiều cao thang cần leo.
