Trạm xe BUS!

[nguyentientu4497]

Lâu lâu có dịp vào lại diễn đàn, hôm nay mình có 1 bài toán cho các bạn thảo luận ^^:
Mỗi ngày có 1 chuyến xe buýt chở N vị hành khách qua P trạm xe buýt khác nhau, đi lần lượt từ trạm 1 đến trạm thứ P.
Trên xe buýt, chỗ đứng thì vô tư, nhưng chỉ có M ghế ngồi mà thôi.
Mỗi người đều có một mức độ thoải mái riêng (giữa 2 người có thể giống hoặc khác nhau) khi ngồi hoặc đứng khi đi từ trạm i qua trạm thứ i+1. Sau khi đã khảo sát được mức độ thoải mái của 1 người là a khi ngồi và b khi đứng, chủ xe muốn thiết lập việc sắp xếp chỗ ngồi sao cho khi đi từ trạm 1 đến trạm P, tổng độ thoải mái là lớn nhất.
TRAM.INP
- Dòng đầu tiên là 3 số N, M, P. (1<=N, M<=100000; 2<=P<=100000)
- Chứa 4 số theo mẫu sau: a b c d.
+ a: độ thoải mái của vị hành khách khi ngồi.
+ b: độ thoải mái của vị hành khách khi đứng.
+ c: vị hành khách đi từ trạm thứ c.
+ d: vị hành khách xuống ở trạm d.
( |a|, |b| <=1000000000)
TRAM.OUT
- Độ thoải mái lớn nhất.

VD:
TRAM.INP

4 2 4
10 -10 2 3
-1 -3 1 4
6 -6 1 3
7 4 2 4

TRAM.OUT

28

Chú ý: thời gian chạy không quá 2s. <Code cẩn thận, suy nghĩ cẩn thận, dễ sai [IMG]data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAA l21bKAAAAA1BMVEXh5PJm+yKVAAAAAXRSTlMAQObYZgAAAApJR EFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=[/IMG]>
P/s: bản thân mình cũng được 90% test thôi ^^. Lố giờ.

[nguyenhungcase]

ôi trời ơi, hổ thẹn thay! Em là học sinh chuyên tin ấy thế mà nhìn vào bài này thấy mù tịt về hướng đi. Các anh chị có cách gì đối với bài này không ạ? Xin cho em được mở rộng tầm hiểu biết.

[hunghk]

Bài này tớ cũng bí lù thuật toán tối ưu [IMG]data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAA l21bKAAAAA1BMVEXh5PJm+yKVAAAAAXRSTlMAQObYZgAAAApJR EFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=[/IMG]. Vẫn không vượt qua được về mặt thời gian của 10% test lớn cuối. Vì vậy mới đưa ra thảo luận ^^.
- Sắp xếp lại.
- Duyệt.
[IMG]data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAA l21bKAAAAA1BMVEXh5PJm+yKVAAAAAXRSTlMAQObYZgAAAApJR EFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=[/IMG]

[mypham]

Thấy có mùi qhd, khổ nỗi mình hơi đuối phần này.

[trangnt]

Thấy có mùi qhd, khổ nỗi mình hơi đuối phần này.

Không có cơ sở QHD đâu anh! :|

[tungloiloi1]

Là do mình chưa tìm ra thôi chứ không phải không có cơ sở qhd. Nói không có cơ sở qhd liệu có phải vội vàng quá không?

[nguyenthoa]

Là do mình chưa tìm ra thôi chứ không phải không có cơ sở qhd. Nói không có cơ sở qhd liệu có phải vội vàng quá không?

Bài này chỉ có 1 đoạn "giống" qhđ chỗ là mỗi lần từ trạm i qua i+1 tối ưu thì kết quả tối ưu.
Nếu có bài toán cơ sở thì dựa vào chia cái gì ra được :|
Suy nghĩ lâu lắm rồi vẫn không có 1 hệ thức truy hồi cho qhđ [IMG]data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAA l21bKAAAAA1BMVEXh5PJm+yKVAAAAAXRSTlMAQObYZgAAAApJR EFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=[/IMG]