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
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.


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);
for i:=1 to n do
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();
}


{$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.