BINLADEN - Bin Laden
Giới hạn- Thời gian: 0.2s
- Bộ nhớ: 1536MB
- Mã nguồn: 50000 bytes
Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.
Trùm khủng bố Bin Laden trốn trong 1 căn hầm được đào sâu xuống mặt đất M tầng, mỗi tầng có N phòng. Các phòng được ngăn cách bằng các cửa rất khó phá. Các phòng có cửa xuống phòng ngay phía dưới và 2 phòng ở 2 bên. Từ trên mặt đất có N cửa xuống N phòng tầng -1. Bin Laden ở tầng dưới cùng (tầng -M) phòng thứ N (phòng ở bên phải nhất). Mỗi cửa được làm bằng một kim loại khác nhau với độ dày khác nhau nên việc phá cửa cần thời gian khác nhau.
Bạn hãy tìm cách đi từ mặt đất xuống phòng của Bin Laden nhanh nhất không hắn thoát mất.
Dữ liệu
- Dòng 1 ghi M và N
- Dòng 2 đến 2M + 1, dòng chẵn ghi N số, dòng lẻ ghi N - 1 số là chi phí để phá cửa.
Kết quả
Ghi ra 1 số là thời gian nhỏ nhất để đến được phòng của Bin Laden
Ví dụ
Dữ liệu 4 2 99 10 1 10 99 1 99 10 1 10 99 1 Kết quả 44 +--99--+--10--+ | | | | 1 | | | | +--10--+--99--+ | | | | 1 | | | | +--99--+--10--+ | | | | 1 | | | | +--10--+--99--+ | | | | 1 | | | | +------+------+ Đi theo đường zigzac
Giới hạn
- 1 <= M <= 2222
- 1 <= N <= 10
- Chi phí của các cánh cửa thuộc [0, 1000].
- Người up: voj
- Nguồn bài: VNOI Marathon '08 - Round 12/DivBProblem Setter: Lê Ðôn Khuê