本来是USACO Training的1.4.1的,但是介于今早过了食物链想起了这道题实在是太怨念了,翻出自己写的AC程序居然有5KB!!
思路很简单,枚举,而且就图中的六种情况。但是第六种变化状况太多了,我自己根本就没写出来后来是看别人写的分四种情况Blah Blah...
可参考此篇中的分析:http://blog.sina.com.cn/s/blog_5c717d190100qgkr.html
program packrec; var r,rw,rt:array[1..4,1..2] of integer; i,j,k,l,t,i1,j1,k1,l1:integer; ans,anscount:integer; ansx,ansy:array [0..200] of integer; procedure swap(var a,b:integer); var t:integer; begin t:=a;a:=b;b:=t; end; procedure panding(x,y:integer); begin if x*y<ans then begin ans:=x*y; anscount:=1; ansx[anscount]:=x; ansy[anscount]:=y; exit; end; if x*y=ans then begin inc(anscount); ansx[anscount]:=x; ansy[anscount]:=y; end; end; procedure work; var lx,ly,min,i,max:integer; begin {layout1} lx:=rw[1,1]+rw[2,1]+rw[3,1]+rw[4,1]; ly:=0; for i:=1 to 4 do if rw[i,2]>ly then ly:=rw[i,2]; panding(lx,ly); {layout2} lx:=rw[1,1]+rw[2,1]+rw[3,1]; if rw[4,1]>lx then lx:=rw[4,1]; max:=0; for i:=1 to 3 do if rw[i,2]>max then max:=rw[i,2]; ly:=max+rw[4,2]; panding(lx,ly); {layout3} lx:=rw[1,1]+rw[2,1]; if rw[3,1]>lx then lx:=rw[3,1]; lx:=lx+rw[4,1]; ly:=rw[1,2]+rw[3,2]; if rw[2,2]>rw[1,2] then ly:=rw[2,2]+rw[3,2]; if rw[4,2]>ly then ly:=rw[4,2]; panding(lx,ly); {layout4} if rw[2,1]>rw[3,1] then lx:=rw[2,1] else lx:=rw[3,1]; lx:=lx+rw[1,1]+rw[4,1]; ly:=rw[1,2]; if rw[2,2]+rw[3,2]>ly then ly:=rw[2,2]+rw[3,2]; if rw[4,2]>ly then ly:=rw[4,2]; panding(lx,ly); {layout5} if rw[1,1]>rw[2,1] then lx:=rw[1,1] else lx:=rw[2,1]; lx:=lx+rw[3,1]+rw[4,1]; ly:=rw[1,2]+rw[2,2]; if rw[3,2]>ly then ly:=rw[3,2]; if rw[4,2]>ly then ly:=rw[4,2]; panding(lx,ly); {layout6} {if (rw[1,1]+rw[3,1]>rw[2,1]+rw[4,1]) then lx:=rw[1,1]+rw[3,1] else lx:=rw[2,1]+rw[4,1]; if rw[1,2]+rw[2,2]>rw[3,2]+rw[4,2] then ly:=rw[1,2]+rw[2,2] else ly:=rw[3,2]+rw[4,2]; if (rw[3,2]>rw[1,2]) and (rw[1,1]<rw[2,1]) then ly:=rw[2,2]+rw[4,2]; if (rw[1,1]>rw[2,1]) and (rw[3,2]>rw[2,2]) then ly:=rw[1,1]+rw[3,2]; if (rw[1,1]>rw[2,1]) and (rw[3,2]>rw[)} if rw[1,2]+rw[2,2]>rw[3,2]+rw[4,2] then ly:=rw[1,2]+rw[2,2] else ly:=rw[3,2]+rw[4,2]; if rw[2,2]>=rw[3,2]+rw[4,2] then begin lx:=rw[1,1]; if rw[3,1]+rw[2,1]>lx then lx:=rw[3,1]+rw[2,1]; if rw[4,1]+rw[2,1]>lx then lx:=rw[4,1]+rw[2,1]; end; if (rw[2,2]>rw[4,2]) and (rw[2,2]>rw[3,2]+r[4,2]) then begin lx:=rw[1,1]+rw[3,1]; if rw[2,1]+rw[3,1]>lx then lx:=rw[2,1]+rw[3,1]; if rw[2,1]+rw[4,1]>lx then lx:=rw[2,1]+rw[4,1]; end; if (rw[4,2]>rw[2,2]) and (rw[4,2]<rw[1,2]+rw[2,2]) then begin lx:=rw[1,1]+rw[3,1]; if rw[1,1]+rw[4,1]>lx then lx:=rw[1,1]+rw[4,1]; if rw[2,1]+rw[4,1]>lx then lx:=rw[2,1]+rw[4,1]; end; if (rw[4,2]>=rw[1,2]+rw[2,2]) then begin lx:=rw[3,1]; if rw[1,1]+rw[4,1]>lx then lx:=rw[1,1]+rw[4,1]; if rw[2,1]+rw[4,1]>lx then lx:=rw[2,1]+rw[4,1]; end; if rw[2,2]=rw[4,2] then begin lx:=rw[1,1]+rw[3,1]; if rw[2,1]+rw[4,1]>lx then lx:=rw[2,1]+rw[4,1]; end; panding(lx,ly); end; begin assign(input,‘packrec.in‘);reset(input); assign(output,‘packrec.out‘);rewrite(output); ans:=32766; for i:=1 to 4 do readln(r[i,1],r[i,2]); for i:=1 to 4 do for j:=1 to 4 do if (j<>i) then for k:=1 to 4 do if (k<>i) and (k<>j) then for l:=1 to 4 do if (l<>i) and (l<>j) and (l<>k) then begin rw[1,1]:=r[i,1];rw[1,2]:=r[i,2]; rw[2,1]:=r[j,1];rw[2,2]:=r[j,2]; rw[3,1]:=r[k,1];rw[3,2]:=r[k,2]; rw[4,1]:=r[l,1];rw[4,2]:=r[l,2]; rt:=rw; for i1:=0 to 1 do for j1:=0 to 1 do for k1:=0 to 1 do for l1:=0 to 1 do begin rw:=rt; if i1=1 then swap(rw[1,1],rw[1,2]); if j1=1 then swap(rw[2,1],rw[2,2]); if k1=1 then swap(rw[3,1],rw[3,2]); if l1=1 then swap(rw[4,1],rw[4,2]); work; end; end; writeln(ans); for i:=1 to anscount-1 do for j:=i+1 to anscount do if ansx[i]<ansx[j] then begin swap(ansx[i],ansx[j]); swap(ansy[i],ansy[j]); end; for i:=1 to anscount do if (ansx[i]<>ansx[i-1]) and (ansx[i]>=ansy[i]) then writeln(ansy[i],‘ ‘,ansx[i]); close(input);close(output); end.
通过日期是2013-11-08,也就是因为NOIP和学农撞日期旷课在家的那个周五0 0,简直是无法忘记那天有多么郁闷,备考的一天简直废在这题上面…⊙﹏⊙b