bài giải MTJUMP spoj – 21948. Nhảy…

các bạn có thể nộp bài tại đây: http://www.spoj.com/THPTCBT/problems/MTJUMP/

1. Đề bài MTJUMP spoj

Trên trục tọa độ Ox có N vị trí được đánh dấu sẵn, vị trí i có tọa độ Xi . Xét một trò chơi như sau:

Nhiệm vụ chính của bạn sẽ thực hiện các bước nhảy giửa các điểm đã đánh dấu. Trước khi bắt đầu trò chơi bạn phải chọn điểm bắt đầu (là một trong N vị trí đã đánh dấu) và chiều nhảy thuận theo chiều tia Ox hoặc ngược lại. Bạn được thực hiện số bước nhảy tùy ý với điều kiện chiều nhảy phải giống nhau và độ dài bước nhảy phải là một số dương và lớn hơn hoặc bằng bước nhảy liền trước. Tất nhiên với những điều kiện này bạn không thể thực hiện quá N bước nhảy. Mỗi vị trí i có một số điểm tương ứng là Pi, điểm của bạn là tổng số điểm các vị trí bạn đến được (bao gồm cả điểm xuất phát).

Yêu Cầu: Tìm cách nhảy để đạt được số điểm lớn nhất.

Dữ Liệu

Vào từ File

–          Dòng đầu ghi số nguyên dương N (1<N<1000)

–          N dòng tiếp theo mỗi dòng thứ i ghi 2 số nguyên tương ứng là Xi, P­i. (1<Xi, Pi<106)

Kết Quả

Ghi ra File

  • Một số duy nhất là số điểm lớn nhất đạt được.

Example

Input:
6
5 6
1 1
10 5
7 6
4 8
8 10

Output:
25
Giải thích: Các vị trí nhảy qua: 4  5  7  10 (tương ứng điểm nhận được: 8+6+6+5=25)

2. Hướng Dẫn MTJUMP spoj

            Để đơn giản ta có thể xem như các vị trí đã được sắp xếp tăng dần theo Xi. Ngoài ra ta chỉ xét việc nhảy theo chiều Xi tăng, việc nhảy ngược lại có thể được làm tương tự bằng cách đảo dấu các tọa độ Xi và thứ tự các vị trí.

  • Gọi F[i, j] là số điểm đạt được lớn nhất có thể nếu vị trí cuối cùng là vị trí j và vị trí liền trước là i.
  • Gọi k là vị trí liền trước i, ta có X[i]-X[k]<=X[j]-X[i].

Do đó F[i, j]= Max{F[k,i] / “k liền trước i}+P[j]

3. code tham khảo MTJUMP spoj

a. Code c++ MTJUMP spoj

b. Code pascal MTJUMP spoj

[/sociallocker]

Trả lời

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *