# CEOI1997 Dominoes多米诺骨牌问题

CEOI1997 Dominoes 多米诺骨牌问题 问题描述:

domino.in 4 61 15 13 12 domino.out 1

- 1 -

2012-06-27

CEOI1997 Dominoes 多米诺骨牌问题
const maxn=1000; maxdot=6; type gaptype=array[-maxdot*maxn..maxdot*maxn] of integer; var fin,fout:text; domino:array[1..maxn] of integer; {domino 记录每块骨牌的两个数的差值} gap,addgap,g:gaptype; i,j,k,a,b,min,max,n:integer; begin assign(fin,'domino8.in');reset(fin); assign(fout,'domino.out');rewrite(fout); readln(fin,n); for i:=1 to n do begin readln(fin,a,b); domino[i]:=a-b; {保留两个数的差} end; for i:=-maxdot*maxn to maxdot*maxn do begin gap[i]:=maxn; addgap[i]:=maxn; end; gap[0]:=0; {初始假设没有骨牌需要翻转就可以做到上下层差值为 0} min:=0; max:=0; for i:=1 to n do{从左到右逐一加入骨牌} begin for j:=min to max do if gap[j]<maxn then begin k:=j+domino[i]; {第 i 块骨牌不动} if gap[j]<addgap[k] then addgap[k]:=gap[j]; k:=j-domino[i]; {第 i 块骨牌翻转一次} if gap[j]+1<addgap[k] then addgap[k]:=gap[j]+1; gap[j]:=maxn; end; min:=min-abs(domino[i]); {计算可能达到的最小和最大的上下层差值} max:=max+abs(domino[i]); g:=gap; gap:=addgap; addgap:=g; {交换运算数组，准备加入下一块骨牌} end; min:=maxn;k:=-1; repeat inc(k); if gap[k]<min then min:=gap[k]; if gap[-k]<min then min:=gap[-k]; until min<maxn; writeln(fout,min); close(fin);close(fout); end.

- 2 -

2012-06-27