比赛 10101115 评测结果 AAAEEEEEEE
题目名称 矩形分割 最终得分 30
用户昵称 nick09 运行时间 0.000 s
代码语言 Pascal 内存使用 0.00 MiB
提交时间 2010-11-15 09:24:19
显示代码纯文本
  1. var
  2. head,tail,tot,i,j,k,n,m,min:longint;
  3. dn,dm:array[1..300]of longint;
  4. a,pn,pm:array[0..1000000]of int64;
  5.  
  6. procedure go;
  7. var i,j:longint;
  8. begin
  9.  
  10. if pn[head]+2<=n then begin
  11. inc(tail);pn[tail]:=pn[head]+1;pm[tail]:=pm[head];
  12. a[tail]:=a[head]+dn[pn[tail]]*(pm[tail]+1); end;
  13. if pm[head]+2<=m then begin
  14. inc(tail);pm[tail]:=pm[head]+1;pn[tail]:=pn[head];
  15. a[tail]:=a[head]+dm[pm[tail]]*(pn[tail]+1); end;
  16. inc(head);
  17. if (pn[tail]+1=n)and(pm[tail]+1=m)and(a[tail]<min) then min:=a[tail];
  18. end;
  19.  
  20. Begin
  21. assign(input,'cut.in');reset(input);
  22. assign(output,'cut.out');rewrite(output);
  23. readln(n,m);
  24. for i:=1 to n-1 do read(dn[i]);
  25. for i:=1 to m-1 do read(dm[i]);
  26. if n=2 then if dn[1]<dn[2] then begin k:=dn[1];dn[1]:=dn[2];dn[2]:=k; end;
  27. if n>2 then
  28. for i:=1 to n-2 do
  29. for j:=i+1 to n-1 do
  30. if dn[i]<dn[j] then begin k:=dn[i];dn[i]:=dn[j];dn[j]:=k;end;
  31. if m=2 then if dm[1]<dm[2] then begin k:=dm[1];dm[1]:=dm[2];dm[2]:=k;end;
  32. if m>2 then
  33. for i:=1 to m-2 do
  34. for j:=i+1 to m-1 do
  35. if dm[i]<dm[j] then begin k:=dm[i];dm[i]:=dm[j];dm[j]:=k ; end;
  36.  
  37. tot:=0;head:=0;tail:=0;min:=maxlongint;pn[0]:=0;pm[0]:=0;
  38. fillchar(a,sizeof(a),0);
  39. repeat
  40.  
  41. go;
  42.  
  43. until head>tail;
  44.  
  45. writeln(min);
  46. end.