Hướng dẫn giải của Lazy Cows
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 ladpro98
program lazycows; uses math; type e=record x,y:longint; end; const s:array[1..4] of longint = (1,1,2,2); fi=''; maxn=1001; maxk=1001; oo=31*trunc(1e6); var n,k,b,d,res,t,tt:longint; a:array[1..maxn] of e; f:array[0..maxn,0..maxk,1..4] of longint; p,pos:array[0..maxn] of longint; inp:text; procedure sort(l,r:longint); var p,t:e; i,j:longint; begin if l>=r then exit; p:=a[random(r-l+1)+l]; i:=l;j:=r; 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 begin t:=a[i]; a[i]:=a[j]; a[j]:=t; end; inc(i);dec(j); end; until i>j; sort(l,j);sort(i,r); end; procedure enter; var j:longint; begin readln(inp,n,k,b); for j:=1 to n do readln(inp,a[j].x,a[j].y); d:=0; sort(1,n); j:=1; while j<=n do begin if pos[d]=a[j].y then p[d]:=3 else begin inc(d); p[d]:=3-a[j].x; pos[d]:=a[j].y; end; inc(j); end; end; procedure dp; var i,j,t,c:longint; begin for j:=0 to k do for t:=1 to 4 do f[1,j,t]:=oo; for j:=1 to k do begin f[1,j,1]:=1; f[1,j,2]:=1; f[1,j,3]:=2; if j>=2 then f[1,j,4]:=2 else f[1,j,4]:=oo; if p[1]=1 then f[1,j,2]:=oo; if p[1]=2 then f[1,j,1]:=oo; if p[1]=3 then begin f[1,j,2]:=oo; f[1,j,1]:=oo; end; end; for i:=2 to d do begin for t:=1 to 4 do f[i,0,t]:=oo; c:=pos[i]-pos[i-1]; for j:=1 to k do begin f[i,j,1]:=min(f[i-1,j,1]+s[1]*c,f[i-1,j-1,1]+s[1]); f[i,j,1]:=min(f[i,j,1],f[i-1,j-1,2]+s[1]); f[i,j,1]:=min(f[i,j,1],f[i-1,j-1,3]+s[1]); f[i,j,1]:=min(f[i,j,1],min(f[i-1,j-1,4]+s[1],f[i-1,j,4]+s[1]*c)); f[i,j,2]:=min(f[i-1,j,2]+s[2]*c,f[i-1,j-1,2]+s[2]); f[i,j,2]:=min(f[i,j,2],f[i-1,j-1,1]+s[2]); f[i,j,2]:=min(f[i,j,2],f[i-1,j-1,3]+s[2]); f[i,j,2]:=min(f[i,j,2],min(f[i-1,j-1,4]+s[2],f[i-1,j,4]+s[2]*c)); f[i,j,3]:=min(f[i-1,j-1,1]+s[3],f[i-1,j-1,2]+s[3]); f[i,j,3]:=min(f[i,j,3],min(f[i-1,j,3]+s[3]*c,f[i-1,j-1,3]+s[3])); f[i,j,3]:=min(f[i,j,3],f[i-1,j-1,4]+s[3]); f[i,j,4]:=min(f[i-1,j-1,2]+c+1,f[i-1,j-1,1]+c+1); f[i,j,4]:=min(f[i,j,4],f[i-1,j,4]+c*s[4]); if j>2 then begin f[i,j,4]:=min(f[i,j,4],f[i-1,j-2,3]+s[4]); f[i,j,4]:=min(f[i,j,4],f[i-1,j-2,4]+s[4]); f[i,j,4]:=min(f[i,j,4],f[i-1,j-2,2]+s[4]); f[i,j,4]:=min(f[i,j,4],f[i-1,j-2,1]+s[4]); end; if p[i]=1 then f[i,j,2]:=oo; if p[i]=2 then f[i,j,1]:=oo; if p[i]=3 then begin f[i,j,1]:=oo; f[i,j,2]:=oo; end; end; end; res:=oo; for t:=1 to 4 do res:=min(res,f[d,k,t]); end; begin assign(inp,fi);reset(inp); readln(inp,t); for tt:=1 to t do begin enter; dp; writeln(res); end; end.
Code mẫu của RR
//Written by Nguyen Thanh Trung {$R+,Q+} {$Mode objFPC} uses math; const FINP = ''; FOUT = ''; MAXN = 1011; oo = 100111000; type rec = record c,h:longint; end; var f1,f2 : text; n,k,b,test : longint; pos : array[1..MAXN] of rec; dd : array[1..2,1..MAXN] of longint; c,ind : array[1..MAXN] of longint; f : array[1..MAXN,-1..MAXN,1..4] of longint; procedure openF; begin assign(f1,FINP); reset(f1); assign(f2,FOUT); rewrite(f2); end; procedure closeF; begin close(f1); close(f2); end; procedure inp; var i:longint; begin read(f1,n,k,b); for i:=1 to n do with pos[i] do read(f1,h,c); end; procedure swap(var a,b:longint); inline; var temp:longint; begin temp:=a; a:=b; b:=temp; end; procedure sort(l,r:longint); inline; var i,j,mid:longint; begin i:=l; j:=r; mid:=c[l+random(r-l+1)]; repeat while c[i]<mid do inc(i); while c[j]>mid do dec(j); if i<=j then begin swap(c[i],c[j]); swap(ind[i],ind[j]); inc(i); dec(j); end; until i>j; if i<r then sort(i,r); if l<j then sort(l,j); end; procedure RR; var i:longint; begin for i:=1 to n do begin c[i]:=pos[i].c; ind[i]:=i; end; sort(1,n); b:=1; pos[ind[1]].c:=1; for i:=2 to n do if c[i]>c[b] then begin inc(b); c[b]:=c[i]; pos[ind[i]].c:=b; end else pos[ind[i]].c:=b; for i:=1 to n do dd[pos[i].h,pos[i].c]:=1; end; procedure update(var u:longint; v:longint); inline; begin u:=min(u,v); end; procedure init; var i,j,ii:longint; begin for ii:=1 to b do for i:=-1 to k do for j:=1 to 4 do f[ii,i,j]:=oo; if (dd[1,1]=0) and (dd[2,1]=1) then begin f[1,1,2]:=1; f[1,1,3]:=2; f[1,2,4]:=2; end else if (dd[1,1]=1) and (dd[2,1]=0) then begin f[1,1,1]:=1; f[1,1,3]:=2; f[1,2,4]:=2; end else if (dd[1,1]=1) and (dd[2,1]=1) then begin f[1,1,3]:=2; f[1,2,4]:=2; end; end; procedure solve; var i,j:longint; begin for i:=2 to b do if (dd[1,i]=0) and (dd[2,i]=1) then for j:=1 to k do begin //Last=2 f[i,j,2]:=min(f[i-1,j,2],f[i-1,j,4])+c[i]-c[i-1]; update( f[i,j,2],min(f[i-1,j-1,1],f[i-1,j-1,2])+1 ); update( f[i,j,2],min(f[i-1,j-1,3],f[i-1,j-1,4])+1 ); //Last=3 f[i,j,3]:=f[i-1,j,3]+(c[i]-c[i-1])<<1; update( f[i,j,3],min(f[i-1,j-1,1],f[i-1,j-1,2])+2 ); update( f[i,j,3],min(f[i-1,j-1,3],f[i-1,j-1,4])+2 ); //Last=4 f[i,j,4]:=f[i-1,j,4]+(c[i]-c[i-1])<<1; update( f[i,j,4],min(f[i-1,j-1,1],f[i-1,j-1,4])+1+c[i]-c[i-1] ); end else if (dd[1,i]=1) and (dd[2,i]=0) then for j:=1 to k do begin //Last=1 f[i,j,1]:=min(f[i-1,j,1],f[i-1,j,4])+c[i]-c[i-1]; update( f[i,j,1],min(f[i-1,j-1,1],f[i-1,j-1,2])+1 ); update( f[i,j,1],min(f[i-1,j-1,3],f[i-1,j-1,4])+1 ); //Last=3 f[i,j,3]:=f[i-1,j,3]+(c[i]-c[i-1])<<1; update( f[i,j,3],min(f[i-1,j-1,1],f[i-1,j-1,2])+2 ); update( f[i,j,3],min(f[i-1,j-1,3],f[i-1,j-1,4])+2 ); //Last=4 f[i,j,4]:=f[i-1,j,4]+(c[i]-c[i-1])<<1; update( f[i,j,4],min(f[i-1,j-1,2],f[i-1,j-1,4])+1+c[i]-c[i-1] ); end else if (dd[1,i]=1) and (dd[2,i]=1) then for j:=1 to k do begin //Last=3 f[i,j,3]:=f[i-1,j,3]+(c[i]-c[i-1])<<1; update( f[i,j,3],min(f[i-1,j-1,1],f[i-1,j-1,2])+2 ); update( f[i,j,3],min(f[i-1,j-1,3],f[i-1,j-1,4])+2 ); //Last=4 f[i,j,4]:=f[i-1,j,4]+(c[i]-c[i-1])<<1; update( f[i,j,4],min(f[i-1,j-1,1],f[i-1,j-1,4])+1+c[i]-c[i-1] ); update( f[i,j,4],min(f[i-1,j-1,2],f[i-1,j-1,4])+1+c[i]-c[i-1] ); update( f[i,j,4],min(f[i-1,j-2,1],f[i-1,j-2,2])+2 ); update( f[i,j,4],min(f[i-1,j-2,3],f[i-1,j-2,4])+2 ); end; writeln(f2,min(min(f[b,k,1],f[b,k,2]),min(f[b,k,3],f[b,k,4]) ) ); end; begin openF; read(f1,test); for test:=1 to test do begin fillchar(dd,sizeof(dd),0); inp; RR; init; solve; end; closeF; end.
Code mẫu của hieult
#include <cstdio> //#include <conio.h> #define max 1000000000 struct bo { int x,y; }; bo A[1010]; int f[1010][1010][3]; int n,K,kq,sl; int min(int a,int b){ return a<b?a:b; } void Quick_sort(int l, int r) { int i=l,j=r; bo k = A[(l+r)/2]; while(i<=j) { while(A[i].x<k.x || (A[i].x==k.x && A[i].y<k.y)) i++; while(A[j].x>k.x || (A[j].x==k.x && A[j].y>k.y)) j--; if(i<=j) { bo temp=A[i]; A[i] = A[j]; A[j] = temp; i++; j--; } } if(j>l) Quick_sort(l,j); if(r>i) Quick_sort(i,r); } int main() { //freopen("LAZYCOWS.in","r",stdin); int test; scanf("%d",&test); for(int itest=1;itest<=test;itest++) { scanf("%d %d %d",&n,&K,&sl); for(int i = 1;i<=n;i++) scanf("%d %d",&A[i].y,&A[i].x); Quick_sort(1,n); f[1][1][0] = 1; f[1][1][1] = 2; f[1][1][2] = max; f[1][2][2] = 2; for(int i = 2;i<=n;i++) for(int j = 1;j<=K;j++) for(int k = 0;k<=2;k++) { f[i][j][k] = max; if(k ==0) { if(j>1) for(int p = 0;p<=2;p++) f[i][j][k] = min(f[i][j][k],f[i-1][j-1][p]+1); if(i>j) { if(A[i].y==A[i-1].y) f[i][j][k] = min(f[i][j][k],f[i-1][j][0]+A[i].x-A[i-1].x); else f[i][j][k] = min(f[i][j][k],f[i-1][j][2]+A[i].x-A[i-1].x); } } else if(k==1) { if(j>1) for(int p = 0;p<=2;p++) f[i][j][k] = min(f[i][j][k],f[i-1][j-1][p]+2); if(i>j) f[i][j][k] = min(f[i][j][k],f[i-1][j][1]+(A[i].x-A[i-1].x)*2); // printf("\n%d",f[i][j][1]); } else { if(j>2) for(int p = 0;p<=2;p++) f[i][j][k] = min(f[i][j][k],f[i-1][j-2][p]+2); if(j>1) f[i][j][k] = min(f[i][j][k],f[i-1][j-1][0]+A[i].x-A[i-1].x+1); if(i>j) f[i][j][k] = min(f[i][j][k],f[i-1][j][2]+2*(A[i].x-A[i-1].x)); // printf("%d\n",f[i][j][2]); } } kq = max; for(int i = 0;i<=2;i++) kq = min(kq,f[n][K][i]); printf("%d\n",kq); } // getch(); }
Code mẫu của khuc_tuan
uses math; const nmax = 1001; vc = 1000000000; hs : array[0..4] of longint = (0,1,1,2,2); type node = record x,y:longint; end; var n,m,stest,test,k,leng:longint; f:Array[0..nmax,0..nmax,0..4] of longint; b,d:Array[0..nmax] of longint; c:array[0..nmax,0..2] of boolean; a:array[0..nmax] of node; procedure sort(l,r:longint); var i,j,mid,tg:longint; begin i:=l; j:=r; mid:=b[l+random(r-l+1)]; repeat while b[i]<mid do inc(i); while b[j]>mid do dec(j); if i<=j then begin tg:=b[i];b[i]:=b[j];b[j]:=tg; inc(i); dec(j); end; until i>j; if l<j then sort(l,j); if i<r then sort(i,r); end; function find(x:longint):longint; var l,r,mid:longint; begin l:=1;r:=m; while l<=r do begin mid:=(l+r)shr 1; if d[mid]<x then l:=mid+1 else if d[mid]>x then r:=mid-1 else exit(mid); end; end; procedure nhap; var i,j,u,v:longint; begin read(n,k,leng); for i:=1 to n do read(a[i].y,a[i].x); for i:=1 to n do b[i]:=a[i].x; sort(1,n); d[1]:=b[1];m:=1; for i:=2 to n do if b[i]<>b[i-1] then begin inc(m);d[m]:=b[i];end; for i:=1 to n do a[i].x:=find(a[i].x); fillchar(c,sizeof(c),false); for i:=1 to n do c[a[i].x,a[i].y]:=true; end; procedure get(var u:longint;x:longint); begin u:=min(u,x); end; procedure xuly; var i,j,u,v,t,res:longint; k1,k2:boolean; begin for i:=0 to m do for j:=0 to k do for t:=0 to 4 do f[i][j][t]:=vc; f[0][0][0]:=0; for i:=1 to m do for j:=0 to i do begin k1:=c[i][1];k2:=c[i][2]; for t:=0 to 4 do begin if (t=1) and k2 then continue; if (t=2) and k1 then continue; if (t=0)and(k1 or k2) then continue; if t=0 then begin for u:=0 to 4 do get(f[i][j][t],f[i-1][j][u]); end else if (t=1)and(j>=1) then begin for u:=0 to 4 do get(f[i][j][t],f[i-1][j-1][u]+1); get(f[i][j][t],f[i-1][j][1]+d[i]-d[i-1]); get(f[i][j][t],f[i-1][j][3]+d[i]-d[i-1]); end else if (t=2)and(j>=1) then begin for u:=0 to 4 do get(f[i][j][t],f[i-1][j-1][u]+1); get(f[i][j][t],f[i-1][j][2]+d[i]-d[i-1]); get(f[i][j][t],f[i-1][j][3]+d[i]-d[i-1]); end else if (t=3)and(j>=2) then begin for u:=0 to 4 do get(f[i][j][t],f[i-1][j-2][u]+2); get(f[i][j][t],f[i-1][j][3]+2*(d[i]-d[i-1])); get(f[i][j][t],f[i-1][j-1][1]+d[i]-d[i-1]+1); get(f[i][j][t],f[i-1][j-1][2]+d[i]-d[i-1]+1); end else if (t=4)and(j>=1) then begin for u:=0 to 4 do get(f[i][j][t],f[i-1][j-1][u]+2); get(f[i][j][t],f[i-1][j][4]+2*(d[i]-d[i-1])); end; end; end; res:=vc; for i:=0 to 4 do for j:=0 to k do res:=min(res,f[m][j][i]); writeln(res); end; begin assign(input,'');reset(input); assign(output,'');rewrite(output); read(stest); for test:=1 to stest do begin nhap; xuly; end; close(input); close(output); end.
Bình luận