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.

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

Hãy đọc nội quy trước khi bình luận.


Không có bình luận tại thời điểm này.