Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

BINLADEN - Bin Laden

Bin Laden

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].

Được gửi lên bởi:VOJ Team
Ngày:2008-09-05
Thời gian chạy:0.200s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ERL GOSU JS-RHINO NODEJS PERL6 PYPY RUST SED VB.NET
Nguồn bài:VNOI Marathon '08 - Round 12/DivB
Problem Setter: Lê Đôn Khuê

hide comments
2016-06-05 15:42:09
yêu lâm
2016-06-05 15:41:23
Đỗ Xuân Bách

Last edit: 2016-06-05 15:41:46
2015-12-04 05:28:44 Nguyễn Thành Nhân
Dùng DP đúng là thiếu trường hợp đi lên thật, 60%
2015-10-27 19:47:28
Blog Thuật toán SPOJ hy vọng giúp được cho mọi người : http://www.oni.vn/uR57W
2015-10-08 09:35:17
solution : http://www.oni.vn/FMzkG
code : http://www.oni.vn/DyUUn
2015-09-08 14:21:11
https://thewizard6296.wordpress.com/2015/09/04/5/
2015-08-16 16:21:14 Sơn Tùng M-TP
Quy hoạch động đc có 60% là sao? :(
2015-08-13 13:14:30 Hacking to the Gate
Thuật toán SPFA + Small Label First cũng AC với 0.01s. Đơn giản hơn Dijkstra Heap.
2015-08-01 15:16:35 Lê Hoàng Vũ
Bài cũng không khó, cơ mà xây dựng đồ thị dễ lộn (Mình lộn giữa i vs j :v)
2015-04-12 05:10:46 dongnocity
sửa cả buoi sáng, dùng quy hoach động ac. :v
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.