Hướng dẫn giải của Pilots
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 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.
Bình luận