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

#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); }

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.