Hướng dẫn giải của HSG12 Đồng Tháp 2023 - Bài 2
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người làm lời giải.
Nộp code mẫu trước khi tự giải được bài tập là một hành vi có thể bị ban.
Gọi ~F[i]~ là thời gian ngắn nhất khi các xe từ xe ~1~ đến xe ~i~ qua cầu, ta có:
~F[i] = Min{F[j-1] + T(j, i)}, j = 1 \dots i-1~
với ~T(j, i)~ là thời gian để nhóm xe từ xe thứ ~j~ đến thứ ~i~ qua cầu cùng lúc ~T(j, i) = L/min(v_j, \dots v_i)~ khi ~w_j + \dots + w_i \le P~
Độ phức tạp thuật toán: ~O(n^2)~.
Bình luận