Hix ... lâu lắm rùi em mới post bài, có 1 bài khá là khó ^^(theo sức của em) Kính mong mọi người vào giúp sức
Một trung tâm thương mại cao 150 tầng. Trên mỗi tầng đều có các ngân hàng chứa tiền. Tòa nhà bị bọn khủng bố tấn công bằng máy bay. Máy bay cảm tử của bọn khủng bố đâm vào tầng j của tòa nhà và gấy ra cháy. Đám cháy này lan từ tầng k xuống với tốc độ 10 phút/tầng. Một tên cướp đang ở tầng 1 thấy đây là một thời cơ để kiếm tiền vì lúc này mọi người đều lo thoát thân. Hắn ta sử dụng 1 thang máy đặc biệt để đi lấy tiền. Thang máy này có tốc độ là 1 phút/tầng. Nếu dừng lại để lấy tiền ở mỗi tầng hắn mất 15 phút. Nhân chứng cho thấy rằng hắn có số liệu về lượng tiền có ở mỗi tầng. Sau khi đám cháy được dập tắt và người ta đang thống kê thiệt hại. Do tài liệu sổ sách về số tiền có trước khi tòa nhà bị khủng bố và một số lượng tiền đã bị cháy nên người ta không thể biết được là tên cướp đã lấy được bao nhiêu tiền. Vì vậy cảnh sát đã nhờ 1 trung tâm Tin học kiểm tra xem số tiền tối đa mà tên cướp có thể lấy được.
Dữ liệu vào: Từ WTC.INP
-Dòng đầu chứa số K (0<K<=150) là tầng mà máy bay của tên khủng bố đã đâm vào.
-Dòng tiếp theo ghi các số t[2],t[3],...,t[k-1] tương ứng là số tiền có ở mỗi tầng 2,3,...k-1
Kết quả: ghi vào WTC.OUT
-Dòng đầu tiên ghi số tiền lớn nhất mà tên cướp có thể lấy.
-Dòng 2 ghi số hiệu các tầng mà tên cướp đã dừng lại để lấy.
Ví dụ:
WTC.INP
10
2 3 4 5 6 7 8 9
WTC.OUT
19
7 6 4 2
Em cần thuật toán tốt để giải quyết bài toán này .... em nghĩ là vét cạn sẽ rất lâu @_@
Bookmarks