Hướng dẫn giải của Hội trường
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này
Code mẫu của flashmt
const maxn=10000; maxs=30000; var n,num:longint; a:array[0..maxn,0..1] of longint; b,c:array[0..maxs] of longint; procedure rf; var i:longint; begin readln(n); for i:=1 to n do readln(a[i,0],a[i,1]); end; procedure sort(l,r:longint); var i,j,x:longint; begin i:=l; j:=r; x:=a[(i+j) div 2,1]; repeat while a[i,1]<x do i:=i+1; while a[j,1]>x do j:=j-1; if i<=j then begin a[0]:=a[i]; a[i]:=a[j]; a[j]:=a[0]; i:=i+1; j:=j-1; end; until i>j; if i<r then sort(i,r); if l<j then sort(l,j); end; function bs(t,num:longint):longint; var l,r,m:longint; begin l:=1; r:=num; m:=0; while l<=r do begin m:=(l+r) div 2; if b[m]=t then break else begin if b[m]>t then r:=m-1 else l:=m+1; end; end; while (b[m]>t) and (m>0) do dec(m); bs:=m; end; procedure pr; var i,t,u,k:longint; begin sort(1,n); fillchar(b,sizeof(b),0); fillchar(c,sizeof(c),0); num:=0; for i:=1 to n do begin t:=a[i,0]; u:=a[i,1]; k:=bs(t,num); if (c[k]+u-t>c[num]) then begin num:=num+1; b[num]:=u; c[num]:=c[k]+u-t; end; end; end; procedure wf; begin write(c[num]); end; begin rf; pr; wf; end.
Code mẫu của happyboy99x
#include <cstdio> #include <vector> using namespace std; #define TR(v, it) for(typeof((v).begin()) it = (v).begin(), _e = (v).end(); it != _e; ++it ) #define fi first #define se second #define MAX 30000 typedef pair<int, int> ii; int n; vector<int> req[MAX+5]; int f[MAX+5]; int max( int a, int b ) { return a > b ? a : b; } int main() { scanf( "%d", &n ); for( int i = 0; i < n; ++i ) { int p, k; scanf( "%d%d", &p, &k ); req[k].push_back(p); } f[0] = 0; for( int i = 1; i <= MAX; ++i ) { f[i] = f[i-1]; TR(req[i], it) { //printf( "%d %d %d\n", *it, i, i-*it + f[*it] ); f[i] = max( f[i], i-*it + f[*it] ); } } printf( "%d\n", f[MAX] ); //for( int i = 0; i <= 20; ++i ) printf( "%d ", f[i] ); return 0; }
Code mẫu của ladpro98
program nkrez; uses math; const maxN=10001; fi=''; type offer = record p,k:longint; end; var f:array[0..maxN] of longint; a:array[1..maxN] of offer; n:longint; procedure input; var inp:text; i:longint; begin assign(inp,fi); reset(inp); readln(inp,n); for i:=1 to n do readln(inp,a[i].p,a[i].k); close(inp); end; procedure swap(i,j:longint); var t:offer; begin t:=a[i]; a[i]:=a[j]; a[j]:=t; end; function find(last,key:longint):longint; var l,r,m,k:longint; begin l:=1; r:=last; k:=1; while l<=r do begin m:=(l+r) shr 1; if a[m].k<=key then begin k:=m; l:=m+1; end else r:=m-1; end; exit(k); end; procedure sort(l,r:longint); var pivot,i,j:longint; begin if l>=r then exit; pivot:=a[random(r-l+1)+l].k; i:=l;j:=r; repeat while a[i].k<pivot do inc(i); while a[j].k>pivot do dec(j); if i<=j then begin if i<j then swap(i,j); inc(i); dec(j); end; until i>j; sort(l,j); sort(i,r); end; procedure dp; var i,j:longint; begin f[0]:=0; for i:=1 to n do begin f[i]:=max(a[i].k-a[i].p,f[i-1]); j:=find(i-1,a[i].p); if a[j].k<=a[i].p then f[i]:=max(f[i],a[i].k-a[i].p+f[j]); end; end; begin input; sort(1,n); dp; write(f[n]); end.
Code mẫu của RR
uses math; var res,u,i,n:longint; a,b:array[1..10111] of longint; bit:array[1..30111] of longint; procedure swap(var a,b:longint); var tmp:longint; begin tmp:=a; a:=b; b:=tmp; end; procedure sort(l,r:longint); var i,j,mid:longint; begin i:=l; j:=r; mid:=a[l+random(r-l+1)]; repeat while a[i]<mid do inc(i); while a[j]>mid do dec(j); if i<=j then begin swap(a[i],a[j]); swap(b[i],b[j]); inc(i); dec(j); end; until i>j; if i<r then sort(i,r); if l<j then sort(l,j); end; function get(u:longint):longint; var v:longint; begin if u<=0 then exit(0); v:=u-u and (-u); exit(max(bit[u],get(v))); end; procedure update(u,k:longint); var v:longint; begin bit[u]:=max(bit[u],k); v:=u+u and (-u); if v<=30000 then update(v,k); end; begin read(n); for i:=1 to n do begin read(a[i],b[i]); inc(a[i]); inc(b[i]); end; sort(1,n); for i:=1 to n do begin u:=get(a[i])+b[i]-a[i]; res:=max(res,u); update(b[i],u); end; writeln(res); end.
Code mẫu của hieult
#include <stdio.h> //#include <conio.h> void quickSort(long A[],long d[],long lower,long upper) { long x = A[(lower + upper) / 2]; long i = lower; long j = upper; do{ while(A[i] < x) i ++; while (A[j] > x) j --; if (i <= j) { long tg=A[i]; A[i]=A[j]; A[j]=tg; long tgd=d[i]; d[i]=d[j]; d[j]=tgd; i ++; j --; } }while(i <= j); if (j > lower) quickSort(A,d, lower, j); if (i < upper) quickSort(A,d, i, upper); } main() { long n,p[10000],k[10000],A[10000],d[10000],F[10000],Max,MaxF=0; scanf("%ld",&n); for(long i=0;i<n;i++) { scanf("%ld %ld",&p[i],&k[i]); A[i]=p[i]; d[i]=i; } quickSort(A,d,0,n-1); F[0]=k[d[0]]-p[d[0]]; for(long i=1;i<n;i++) { F[i]=k[d[i]]-p[d[i]]; Max=0; for(int j=0;j<i;j++) if(k[d[j]]<=p[d[i]]&&F[j]>Max) Max=F[j]; F[i]+=Max; } for(long i=0;i<n;i++) if(F[i]>MaxF) MaxF=F[i]; printf("%ld",MaxF); //getch(); }
Code mẫu của ll931110
program NKREZ; const input = ''; output = ''; maxn = 10000; maxk = 30000; type rec = record x,y: integer; end; var a: array[1..maxn] of rec; res: array[0..maxk] of integer; n: integer; procedure init; var f: text; i: integer; begin assign(f, input); reset(f); readln(f, n); for i := 1 to n do readln(f, a[i].x, a[i].y); close(f); end; procedure swap(var u,v: rec); var z: rec; begin z := u; u := v; v := z; end; procedure qsort(l,h: integer); var i,j: integer; p: rec; begin if l >= h then exit; i := l; j := h; p := a[random(h - l + 1) + l]; repeat while a[i].y < p.y do inc(i); while a[j].y > p.y do dec(j); if i <= j then begin if i < j then swap(a[i],a[j]); inc(i); dec(j); end; until i > j; qsort(l,j); qsort(i,h); end; procedure solve; var f: text; i,j,max: integer; begin fillchar(res, sizeof(res), 0); max := a[n].y; res[a[1].y] := a[1].y - a[1].x; for i := 2 to n do begin if a[i].y > a[i - 1].y then for j := a[i - 1].y + 1 to a[i].y do if res[j] < res[a[i - 1].y] then res[j] := res[a[i - 1].y]; if res[a[i].y] < res[a[i].x] + a[i].y - a[i].x then res[a[i].y] := res[a[i].x] + a[i].y - a[i].x; end; assign(f, output); rewrite(f); writeln(f, res[max]); close(f); end; begin init; qsort(1,n); solve; end.
Code mẫu của skyvn97
#include<stdio.h> #include<algorithm> #define MAX 11111 using namespace std; typedef pair<int,int> ii; ii a[MAX]; int n; int f[MAX]; void init(void) { scanf("%d",&n); int i,p,k; for (i=1;i<=n;i=i+1) { scanf("%d",&p); scanf("%d",&k); a[i]=ii(k,p); } sort(&a[1],&a[n+1]); a[0]=ii(0,0); } int bs(int l,int r,int val) { if (l==r) return (r); if (r-l==1) { if (a[r].first<=val) return (r); return (l); } int m=(l+r)/2; if (a[m].first<=val) return (bs(m,r,val)); return (bs(l,m,val)); } void optimize(void) { int i,x; f[0]=0; f[1]=a[1].first-a[1].second; for (i=2;i<=n;i=i+1) { f[i]=f[i-1]; x=bs(0,i-1,a[i].second); if (f[x]+a[i].first-a[i].second>f[i]) f[i]=f[x]+a[i].first-a[i].second; } printf("%d",f[n]); } int main(void) { init(); optimize(); }
Code mẫu của khuc_tuan
#include <iostream> #include <cstdio> #include <vector> using namespace std; int n; int a[10010], b[10010]; vector<int> list[30030]; int F[30030]; int main() { scanf("%d", &n); for(int i=0;i<n;++i) { scanf("%d%d", a+i, b+i); a[i] +=10; b[i] += 10; } for(int i=0;i<n;++i) list[b[i]].push_back(a[i]); F[0] = 0; for(int i=1;i<=30020;++i) { F[i] = F[i-1]; for(int k=0;k<list[i].size();++k) { int j = list[i][k]; F[i] >?= F[j] + i - j; } } cout << F[30020] << endl; //system("pause"); return 0; }
Bình luận