Wtc

[NothingToLost]

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 @_@

[tungnhoi]

Thứ nhất là hình như ví dụ của em sai rồi
Nếu đi từ tầng 1 ---> 2 xong rồi lấy đồ thì mất 1 + 15 = 16 phút
Từ tầng 2 ----> 4 xong rồi lấy đồ thì mất 1*2 + 15 = 17 phút + 16 phút lúc đầu là 33 phút
Mà đã 33 phút thì nó đã lan xuống tầng 7 và cũng ko kịp lên tầng 6 lấy đồ thì làm sao kết quả lại là 2 4 6 7 được

Thứ hai: Tui dùng quy hoạch động để làm bài này

Gọi F[i] là số tiền lớn nhất có thể lấy được khi đi từ tầng 2--->i
t[i] là thời gian để đi

thì ta có f[i]:= max(f[j]) với điều kiện (j= 1..i-1) và t[j] + 15 + 1*(i-j) < 10*(n-i)

Từ đó sẽ ra kết quả lớn nhất rồi truy hồi tìm các tầng

Có gì sai mong các huynh đệ chỉ giáo

[NothingToLost]

Nếu đi từ tầng 1 ---> 2 xong rồi lấy đồ thì mất 1 + 15 = 16 phút
Từ tầng 2 ----> 4 xong rồi lấy đồ thì mất 1*2 + 15 = 17 phút + 16 phút lúc đầu là 33 phút
Mà đã 33 phút thì nó đã lan xuống tầng 7 và cũng ko kịp lên tầng 6 lấy đồ thì làm sao kết quả lại là 2 4 6 7 được

Thứ nhất có lẽ là ông không hiểu ví dụ, tức là lên thẳng tầng 7 lấy tiền rùi xuống đi xuống tầng 6 .... xuống tiếp tầng 4 và tầng 2

Thứ hai: Tui dùng quy hoạch động để làm bài này

Vét cạn và quy hoạch động thì cái nào nhanh hơn ???

[tungnhoi]

Thế cái này đi được nhiều chiều chứ ko phải chỉ là từ dưới đi lên thui hả

[NothingToLost]

Thế cái này đi được nhiều chiều chứ ko phải chỉ là từ dưới đi lên thui hả

Ô hay .... đi thế này tức là đi cướp, phải đi từ tầng 1 lên tầng j nào đó rùi lại phải xuống tầng 1 .... còn lấy tiền sao cho nhiều nhất nữa Có vẻ không dễ đâu
Mới có 1 người tham gia cái thread này >_< Mọi người trong dđ có vẻ thờ ơ quá >_<

[NothingToLost]

Oài ... ko ai giúp cho cái àh. Khinh bài này dễ sao

[rainstorm]

Ê! Cái bài này tui nghĩ là quy hoạch động được đó .
Tính quy hoạch theo hướng đi lên và đi xuống roi cộng vào
cái nào min thì lấy.

[rainstorm]

theo mình nên có một mảng flen {la mang tien khi đi lên} và mảng Fxuong {là mảng tiền đi xuống} mang tg{la mang thoi gian } và mảng đánh dấu tầng nào lấy rồi thì khỏi lấy nữa: dd[i]:byte;
Fxuong[i]:= max {Fxuong[j]} voi 2<=j<= i và dd[i]=0;
Flen[i]:=max {t[j]+ Flen[j-1]} 2<=j<=i và tg[j]+i-j < 10*(k-i);
trong lúc lên , nếu chọn tầng nào lấy tiền thì đánh dấu tầng đó vào dd[j]:=1;
tg[i]:=tg[j]+i-j;

[NothingToLost]

Hơ ... đầu bài này nó yêu cầu là số tiền nhiều nhất cơ mà, nói như bạn thì chưa chính xác rùi

[bete]

Tui xin ké vô 1 chút
Nói chung thì có 3 dạng đường đi: nhiều lần, 1 lần (ngừng lúc lên & xuống), 1 lần (chỉ ngừng lúc xuống).
Mình có thể chứng mình là:
- cho một đường đi loại 1 (nhiều lần) nào đó => luôn có thể đưa về một đường đi loại 3 (1 lần; chỉ ngừng lúc xuống) tương ứng và đường đi loại 3 này không xấu hơn đường đi loại 1 đã cho
- cho một đường đi loại 2 (1 lần; ngừng lúc lên & xuống) nào đó => luôn có thể đưa về một đường đi loại 3 (1 lần; chỉ ngừng lúc xuống) tương ứng và đường đi loại 3 này không xấu hơn đường đi loại 2 đã cho

Tới đây thì mình có thể xài qui hoạch động để tìm đường đi loại 3 tốt nhứt được rồi

(có gì sai sót mong được góp ý, xin cám ơn)

-thân