Tưởng tượng một con đường đơn giản trong hệ tọa độ. Đường đi từ trái sang phải theo hình dạng của mặt đất và trong một ô có thể:
Giữ nguyên độ cao
Đi lên hoặc đi xuống một ô
Ô tô đi trên con đường theo hướng từ trái sang phải. Thời gian cần thiết để đi qua một ô là giây trong trường hợp , hoặc giây trong trường hợp .
Tuy vậy, chúng ta có thể xây dựng một đường hầm dưới những ngọn núi hay một chiếc cầu qua những thung lũng. Những đường hầm hay cầu được xây dựng phải được nằm ngang, chỉ giao cắt với con đường tại hai điểm đầu cuối, và thời gian cần để ô tô di chuyển qua một ô bằng đường hầm hoặc qua cầu là giây.
Viết chương trình tính toán thời gian ngắn nhất để ô tô đi hết cả quãng đường qua những đường hầm và cầu tốt nhất, với hình dạng mặt đất cho trước. Tổng số đường hầm hoặc cầu được xây dựng không lớn hơn số cho trước.
Hình trên là số liệu phù hợp với ví dụ thứ hai (bên dưới). Con đường ban đầu được biểu thị bằng đường kẻ mảnh, và con đường tối ưu được biểu thị bằng đường kẻ đậm. Vì số đường hầm và cầu được hỗ trợ bị hạn chế chỉ có , ta không thể xây dựng đường hầm dưới ngọn núi đầu tiên.
Dữ liệu:
Dòng đầu tiên chứa ba số nguyên ;
Dòng thứ hai chứa hai số nguyên và ;
Dòng thứ ba chứa dãy kí hiệu, mô tả hình dạng của mặt đất từ trái sang phải. Mỗi kí hiệu trong dãy có nghĩa như sau:
D nếu ô tiếp theo trên mặt đất hướng ĐI XUỐNG
R nếu ô tiếp theo trên mặt đất GIỮ NGUYÊN ĐỘ CAO
G nếu ô tiếp theo trên mặt đất hướng ĐI LÊN
Kết quả:
Ghi ra thời gian ngắn nhất kết quả của đề bài đã cho.
