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