当前位置:首页 >> 学科竞赛 >>

CEOI1997 Dominoes多米诺骨牌问题


CEOI1997 Dominoes 多米诺骨牌问题 问题描述:
有一种多米诺骨牌是平面的,其正面被分成上下两部分,每一部分的表面或者为空,或者被标上 1 至 6 个 点。现有一行排列在桌面上:

顶行骨牌的点数之和为 6+1+1+1=9;底行骨牌点数之和为 1+5+3+2=11。顶行和底行的差值是 2。这 个差值是两行点数之和的差的绝对值。每个多米诺

骨牌都可以上下倒置转换,即上部变为下部,下部变为上部。 现在的任务是,以最少的翻转次数,使得顶行和底行之间的差值最小。对于上面这个例子,我们只需翻转最 后一个骨牌,就可以使得顶行和底行的差值为 0,所以例子的答案为 1。

输入格式:
第 1 行是一个整数 n(1 ? n ? 1,000),表示有 n 个多米诺骨牌在桌面上排成一行。 接下来总共有 n 行,每行包含两个整数 a,b(0 ? a,b ? 6,中间用空格分开)。 第 i+1 行的 a,b 分别表示第 i 个多米诺骨牌的上部和下部的点数(0 表示空)。

输出格式:
仅一行一个整数表示翻动骨牌的最少次数,从而使得顶行和底行的差值最小。

输入输出样例:
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


相关文章:
CEOI1997 Dominoes多米诺骨牌问题
CEOI1997 Dominoes 多米诺骨牌问题 问题描述: 有一种多米诺骨牌是平面的,其正面被分成上下两部分,每一部分的表面或者为空,或者被标上 1 至 6 个点。现有一行...
8个不重叠的多米诺骨牌16个单位的板子
8 个不重叠的多米诺骨牌有多少种方法来盖住下面 16 个单位的板 子? Domino 骨牌是什么样子? There is 1 way that we can arrange all 8 dominoes vertically....
拼缀法
她给俄狄浦斯出的问题是:什么东西早晨用四只脚走路,中午用两只 脚走路,傍 ...15、多米诺骨牌 Dominoes 多米诺骨牌 是一种西洋游戏。将许多长方形的骨牌竖立...
常见英语短语的意思
她给俄狄浦斯出的问题是:什么东西早晨用四只脚走路,中午用两只 脚走路,傍 ...15、多米诺骨牌 Dominoes 多米诺骨牌 是一种西洋游戏。将许多长方形的骨牌竖立...
更多相关标签:
多米诺骨牌问题 | hdu多米诺骨牌问题 | dominoes | dominoes游戏规则 | dominoes怎么玩 | double six dominoes | ceoi2011 | ceoi2015 |