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 độ X_i . 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à P_i, đ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à X_i, P_i. (1<X_i, P_i<10⁶)

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 X_i. Ngoài ra ta chỉ xét việc nhảy theo chiều X_i 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 độ X_i 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

#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
#define fi first
#define se second
typedef pair<int,int> ii;
typedef pair<int,ii> ip;
vector<ip> v;
bool cmp1(ip a,ip b){return a.fi<b.fi || (a.fi==b.fi && a.se.se<b.se.se);}
bool cmp2(ip a,ip b){return a.fi<b.fi || (a.fi==b.fi && a.se.fi>b.se.fi);}
int main()
{
    int f[1001],n,i,j,k,ans=0;
    ii p[1001];
    scanf("%d",&n);
    for(i=0;i<n;++i) scanf("%d%d",&p[i].fi,&p[i].se);
    sort(p,p+n);
    for(i=0;i<n;++i)
        for(j=i+1;j<n;++j) v.push_back(ip(p[j].fi-p[i].fi,ii(i,j)));
    sort(v.begin(),v.end(),cmp1);
    for(i=0;i<n;++i) f[i]=p[i].se;
    for(i=0;i<v.size();++i)
    {
        j=v[i].se.fi;k=v[i].se.se;
        f[k]=max(f[k],f[j]+p[k].se);
    }
    for(i=0;i<n;++i)
    {
        ans=max(ans,f[i]);
        f[i]=p[i].se;
    }
    sort(v.begin(),v.end(),cmp2);
    for(i=0;i<v.size();++i)
    {
        j=v[i].se.fi;k=v[i].se.se;
        f[j]=max(f[j],f[k]+p[j].se);
    }
    for(i=0;i<n;++i) ans=max(ans,f[i]);
    printf("%d",ans);
}

b. Code pascal MTJUMP spoj

const   fi='';
        nmax=1000;
type    data=longint;
        dulieu=record
                x,y:data;
        end;
var
        f:text;
        a:array[1..nmax] of dulieu;
        n,ans,i:data;
        C:array[0..nmax+1,0..nmax+1] of data;

procedure docfile;
var     i,j:data;
begin
        assign(f,fi); reset(f);
        readln(f,n);
        for i:=1 to n do
                readln(f,a[i].x,a[i].y);
        close(f);
end;

procedure sort(l,r: longint);
      var
         i,j,x: longint;
         y:dulieu;
      begin
         i:=l;
         j:=r;
         x:=a[(l+r) div 2].x;
         repeat
           while a[i].x<x do
            inc(i);
           while x<a[j].x do
            dec(j);
           if not(i>j) then
             begin
                y:=a[i];
                a[i]:=a[j];
                a[j]:=y;
                inc(i);
                j:=j-1;
             end;
         until i>j;
         if l<j then
           sort(l,j);
         if i<r then
           sort(i,r);
      end;

function max(a,b:data):data;
begin
        if a>b then exit(a);
        exit(b);
end;

procedure xuli;
var     i,j,k,res:data;
begin
        fillchar(c,sizeof(c),0);
        sort(1,n);
        for i:=1 to n do
                C[i,i]:=a[i].y;
        for i:=1 to n do
                for j:=i+1 to n do
                        begin
                                for k:=i downto 1 do
                                        begin
                                                if A[i].x-a[k].x>a[j].x-a[i].x then
                                                        break;
                                                c[i,j]:=max(c[i,j],c[k,i]+a[j].y);
                                        end;
                        end;
        res:=0;
        for i:=1 to n do
                for j:=i to n do
                        res:=max(res,c[i,j]);
        ans:=max(ans,res);
end;

begin
        docfile;
        ans:=0;
        xuli;
        for i:=1 to n do
                a[i].x:=-a[i].x;
        xuli;
        writeln(ans);
end.

[/sociallocker]

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