Căng dây qua cọc
Đề bài
Mô tả
Cho một dãy gồm cái cọc nằm trên một đường thẳng. Cọc thứ nằm ở tọa độ và có chiều cao . Ta cần căng một sợi dây nối cọc với cọc , đi qua một số cọc trung gian (), đặt và . Do ràng buộc kỹ thuật, hai cọc được chọn liên tiếp phải có chiều cao cân bằng và ở gần nhau. Cụ thể, với hai cọc được chọn liên tiếp và (), phải có:
- ;
- .
Hãy chọn tập các cọc trung gian thỏa mãn các ràng buộc trên sao cho tổng chiều cao của các cọc được chọn là nhỏ nhất.
Dữ liệu vào
- Dòng đầu tiên chứa ba số nguyên dương , , (, , ).
- Dòng thứ hai chứa số nguyên dương ().
Dữ liệu ra
In ra tổng chiều cao của các cọc được chọn trong phương án tối ưu, tính cả cọc và cọc . Nếu không có cách chọn nào, in ra .
Ràng buộc
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 13 4 2 4 1 7 2 6 3 5 1 7 5 3 4 3 |
13 | Chọn các cọc , tổng chiều cao là . |
| 6 2 3 2 5 9 4 1 4 |
15 | Ví dụ bổ sung, tính bằng lời giải mẫu. Chọn các cọc , tổng chiều cao là . Từ cọc không thể đi tới cọc vì . |
Bình luận