Dạo này thấy box Pascal ỉu xìu quá!

[F12]

Có vẻ như không cần giới hạn số xăng.

m,n<20, mỗi ô không được đi quá một lần ==> số xăng tối đa trong một bản đồ không quá 20*20*3=1200 ==> 10 bản đồ không quá 12000.

Cũng không cần QHĐ L[i,j], với mỗi bản đồ ta cố gắng sử dụng càng nhiều xăng càng tốt, sau đó cộng Z bản đồ lại.

Nhưng C[i,j] thì loang thế nào nhỉ ? : ) )

Và C[i,j] đâu đã được. Phải xử lý cả ít ô đi qua nhất nữa chứ.

Còn mình chứng minh được bài này NP.

Với bộ nhớ Free thì may ra làm được. Nhưng chắc cũng phải chạy lâu.

[pineflower]

Có vẻ như không cần giới hạn số xăng.

m,n<20, mỗi ô không được đi quá một lần ==> số xăng tối đa trong một bản đồ không quá 20*20*3=1200 ==> 10 bản đồ không quá 12000.

Cũng không cần QHĐ L[i,j], với mỗi bản đồ ta cố gắng sử dụng càng nhiều xăng càng tốt, sau đó cộng Z bản đồ lại.

Nhưng C[i,j] thì loang thế nào nhỉ ? : ) )

Còn mình nghĩ, bài này NP.

Với bộ nhớ Free thì may ra làm được. Nhưng chắc cũng phải chạy lâu.

Ặc thế nhỡ dùng hết xăng giữa đường thì thế nào? Mà bài này đâu gọi là NP được. Thuật toán rõ ràng thế kìa cơ mà. Để giải bài toán C[i,j] bạn đã làm đc rồi mà. Loang : đến ô i,j và tiêu thụ hết k xăng. Vậy C[i,j] = 1 khi và chỉ khi trạng thái M,N,J xuất hiện trong queue.
12000 chạy trong free nhanh thôi mà. Độ phức tạp 12000^2. Thế nên tớ mới nói là trong turbo thì cần phải xem lại số lượng xăng.
Mình xin nói thêm một chi tiết là theo mình hiểu một ô chỉ đi qua không quá 1 lần thì mới có cách giải tốt, còn hơn thì đúng là NP. (Vấn đề này thuộc về đề bài :-D)

[pineflower]

Còn nếu muốn số ô đi qua ít nhất nữa thì chỉ việc thay đổi C[i,j] thành số ô ít nhất mà đi qua hết mê cung i chỉ dùng j nhiên liệu. Cái này chình là D[n,m,j] trong bài giải của cậu. Nếu tớ ko nhầm tên mảng D (^ ^)

[truongngocdai]

Mấy anh nói chuyện PRO quá, chẳng hiểu gì cả
Bài này là em test đấy đó

[F12]

Chết thật, mình tưởng hết xăng giữa đường càng tốt.

Ý bạn pineflower có phải là loang D[i,j,k]. Độ phức tạp là 20*20*12000*4 thôi. Với Free thì chạy tốt đấy.

Mình suy nghĩ rằng bài toán tìm đường đi dài nhất trong đồ thị là NP nên bài này là NP. Nhưng cách giải trên có thêm k vào thì nó có thuật toán tốt rồi.

[Master_Baby]

Thì phải về đến nơi mới hết xăng chứ, ai lại thích hết xăng giữa đường, cả đoạn sau vác robot về ah.
Vả lại, sếp F12 please đọc kỹ đề bài: tiêu nhiều xăng nhứt mà đường đi phải ngắn nhứt. Vậy mà đi lại ô đã đi thì lộ tẩy hết rùi còn gì.

[truongngocdai]

sôi nổi thật. Master_Baby tham gia rồi đó hả

[pineflower]

Chết thật, mình tưởng hết xăng giữa đường càng tốt.

Ý bạn pineflower có phải là loang D[i,j,k]. Độ phức tạp là 20*20*12000*4 thôi. Với Free thì chạy tốt đấy.

Mình suy nghĩ rằng bài toán tìm đường đi dài nhất trong đồ thị là NP nên bài này là NP. Nhưng cách giải trên có thêm k vào thì nó có thuật toán tốt rồi.

he he, độ phức tạp bài này không phải là ở chỗ loang mà là chỗ quy hoạch động. Bạn nên nhớ để tính cho L[i,j] thì phải thử tất cả các L[i - 1,k] (k < j) cho nên độ phức tạp ở đây là x^2 trong đó x là số nhiên liệu. Tuy nhiên tính chính xác ra thì phải cộng thêm độ phức tạp chỗ loang nữa, chính xác là x^2 + x * n * m * k. Độ phức tạp chung x^2.

[truongngocdai]

mấy đại ca giỏi quá, bái phục, bái phục

[truongngocdai]

Làm bài đi mấy đại ca nhé, em ko tham gia vì thuộc BTC, gửi bài giải cho em