Description
Input
输入文件的第一行是一个正整数n(
1≤n≤
1000)，表示多米诺骨牌数。接下来的n行表示n个多米诺骨牌的点数。每行有两个用空格隔开的正整数，表示多米诺骨牌上下方块中的点数
a和b，且
1≤
a，b≤
6。
Output
输出文件仅一行，包含一个整数。表示求得的最小旋转次数。
Sample Input
4
6 1
1 5
1 3
1 2
Sample Output
１
题解：这道题用dp，f[i]表示最小的旋转速度。
if f[i]<>f[-
10000]
then break;
if f[-i]<>f[-
10000]
then break;
var f:array[-
10000..10000]
of longint;
n,i,j,
sum,suma,sumb:longint;
a,b:array[
1..1000]
of longint;
function min(a,b:longint):longint;
begin
if a<b
then exit(
a)
else exit(b);
end;
begin
readln(n);
for i:=
1 to n
do readln(
a[i],b[i]);
for i:=
1 to n
do suma:=suma+
a[i];
for i:=
1 to n
do sumb:=sumb+b[i];
for i:=
1 to n
do sum:=
sum+
a[i]+b[i]-
min(
a[i],b[i]);
fillchar(f,sizeof(f),
127);
f[suma-sumb]:=
0;
for i:=
1 to n
do
begin
if a[i]>b[i]
then
for j:=-
sum to sum do
f[j]:=
min(f[j],f[j+
2*(
a[i]-b[i])]+
1);
if a[i]<b[i]
then
for j:=
sum downto -
sum do
f[j]:=
min(f[j],f[j+
2*(
a[i]-b[i])]+
1);
end;
for i:=
0 to sum do
begin
if f[i]<>f[-
10000]
then break;
if f[-i]<>f[-
10000]
then break;
end;
writeln(
min(f[i],f[-i]));
end.
转载请注明原文地址: https://ju.6miu.com/read-13661.html
