Editorial for Pilots


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

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 fi='';
      fo='';
      maxn=10000;
var n,re:longint;
    f:array[0..1,0..maxn shr 1] of longint;
    a,b:array[0..maxn] of longint;

procedure rf;
var i:longint;
begin
     readln(n);
     for i:=1 to n do readln(a[i],b[i]);
end;

function min(x,y:longint):longint;
begin
     if x<y then min:=x else min:=y;
end;

procedure pr;
var i,j,z:longint;
begin
     for i:=1 to n do
     begin
          z:=i and 1;
          f[z,0]:=f[1-z,0]+b[i];
          for j:=1 to (i-1) shr 1 do
              f[z,j]:=min(f[1-z,j-1]+a[i],f[1-z,j]+b[i]);
          if z=0 then f[z,i shr 1]:=f[1-z,i shr 1-1]+a[i];
     end;
     re:=f[z,n shr 1];
end;

procedure wf;
begin
     writeln(re);
end;

begin
     assign(input,fi); reset(input);
     assign(output,fo); rewrite(output);
     rf;
     pr;
     wf;
     close(input); close(output);
end.

Code mẫu của ladpro98

program mpilot;
uses    math;
const   maxn=10010;
        fi='';
var     x,y:array[0..maxn] of longint;
        f:array[0..maxn] of longint;
        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,x[i],y[i]);
        close(inp);
end;

procedure dp;
var     i,j:longint;
begin
        //f[i,j]=tong min chon 1..i, so lai chinh la j
        for i:=1 to n do
        begin
                if not odd(i) then
                f[i div 2]:=f[i div 2-1]+x[i];
                for j:=(i-1) shr 1 downto 1 do
                f[j]:=min(f[j-1]+x[i],f[j]+y[i]);
                f[0]:=f[0]+y[i];
        end;

end;

begin
        input;
        dp;
        write(f[n shr 1]);
end.

Code mẫu của RR

//Written by RR
#include <vector>
#include <set>
#include <algorithm>
#include <string>
#include <cmath>
#include <queue>
#include <map>
#include <iostream>
#include <list>
#include <deque>
#include <cstdio>
#include <cstdlib>

#define MAXN 10111
#define FOR(i,a,b)  for(long i=a; i<=b; i++)
#define FORD(i,a,b) for(long i=a; i>=b; i--)
#define V vector<long>
#define S set< pair<long,long> >
#define M map<long,long>
#define FORM(i,m)  for(M::iterator i=m.begin(); i!=m.end(); i++)
#define FORS(i,s)  for(S::iterator i=s.begin(); i!=s.end(); i++)
#define FORV(i,v)  for(V::iterator i=v.begin(); i!=v.end(); i++)
#define PB push_back
#define SZ(x) x.size()
#define MP make_pair

using namespace std;

typedef long long       ll;
typedef long double     ld;
typedef vector<bool>    vb;
typedef pair<long,long> ii;

long n,costc[MAXN],costp[MAXN],dd[MAXN];

void inp() {
     scanf("%ld",&n);
     FOR(i,1,n)
       scanf("%ld %ld",&costc[i],&costp[i]);
}

void solve() {
     S s;
     FOR(i,1,n) {
         s.insert( MP(costc[i]-costp[i],i) );
         if (i%2==1) {
                     S::iterator u=s.end(); u--;
                     dd[u->second]=1;
                     s.erase(u);
         }
     }
     long res=0;
     FOR(i,1,n)
       if (dd[i]==0) res+=costc[i];
       else res+=costp[i];
     printf("%ld\n",res);
}

int main() {
    #ifdef DEBUG
      freopen("input.txt","r",stdin);
      freopen("output.txt","w",stdout);
    #endif
    inp();
    solve();
    return 0;
}

Code mẫu của hieult

#include <stdio.h>
//#include <conio.h>
long max(long a,long b)
{
if(a>b) return a;
else return b;
}
main()
{
long n,a[10001],b[10001],c[10001],KQ=0,f[10001][5001];
scanf("%ld",&n);      
for(long i=n;i>=1;i--)
  {
  scanf("%ld %ld",&a[i],&b[i]);
  c[i]=a[i]-b[i];
  KQ+=a[i];  
  }
for(long i=1;i<=n;i++)
  f[i][0]=0;
for(long i=2;i<=n;i++)
  {
  for(long j=1;j<=(i-1)/2;j++)  
    f[i][j]=max(f[i-1][j-1]+c[i],f[i-1][j]);
  if(i%2==0)
    f[i][i/2]=f[i-1][i/2-1]+c[i];
  }    
KQ=KQ-f[n][n/2];     
printf("%ld",KQ);
//getch();
}

Code mẫu của ll931110

{$MODE DELPHI}
Program MPILOT;
Const
  input  = '';
  output = '';
  maxn = 10000;
  maxk = 5000;
  maxv = 500000000;
Var
  a,b: array[1..maxn] of integer;
  t: array[0..maxk,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], b[i]);

  Close(f);
End;

Procedure optimize;
Var
  i,j: integer;
Begin
  For i:= 0 to n div 2 do
    For j:= 0 to n div 2 do t[i,j]:= maxv;

  t[0,0]:= 0;
  For i:= 1 to n div 2 do t[0,i]:= t[0,i - 1] + b[i];

  For i:= 1 to n div 2 do
    For j:= i to n div 2 do
      Begin
        t[i,j]:= t[i - 1,j] + a[i + j];
        If t[i,j] > t[i,j - 1] + b[i + j] then t[i,j]:= t[i,j - 1] + b[i + j];
      End;
End;

Procedure printresult;
Var
  f: text;
Begin
  Assign(f, output);
    Rewrite(f);
    Writeln(f, t[n div 2,n div 2]);
  Close(f);
End;

Begin
  init;
  optimize;
  printresult;
End.

Code mẫu của khuc_tuan

//{$APPTYPE CONSOLE}
 {$MODE DELPHI}

uses
    math;

var
    n, i, j, inf, cur : integer;
    x, y : array[1..10000] of integer;
    f : array[0..5000,0..5000] of integer;
begin
    read(n);
    for i:=1 to n do
    begin
        read(x[i],y[i]);
    end;
    fillchar( f, sizeof(f), $1f);
    inf := f[0,0];
    f[0,0] := 0;
    for i:=0 to n div 2 do
        for j:=0 to i do
            if f[i,j] < inf then
            begin
                cur := i + j + 1;
                if i < 5000 then f[i+1,j] := min( f[i+1,j], f[i,j] + y[cur]);
                if j+1 <= i then f[i,j+1] := min( f[i,j+1], f[i,j] + x[cur]);
            end;
    writeln( f[n div 2, n div 2]);
end.

Comments

Please read the guidelines before commenting.


There are no comments at the moment.