洛谷 P1282 多米諾骨牌
題目
題目描述
多米諾骨牌有上下2個方塊組成,每個方塊中有1~6個點。現有排成行的
上方塊中點數之和記為S1,下方塊中點數之和記為S2,它們的差為|S1-S2|。例如在圖8-1中,S1=6+1+1+1=9,S2=1+5+3+2=11,|S1-S2|=2。每個多米諾骨牌可以旋轉180°,使得上下兩個方塊互換位置。 程式設計用最少的旋轉次數使多米諾骨牌上下2行點數之差達到最小。
對于圖中的例子,隻要将最後一個多米諾骨牌旋轉180°,可使上下2行點數之差為0。
輸入輸出格式
輸入格式:
輸入檔案的第一行是一個正整數n(1≤n≤1000),表示多米諾骨牌數。接下來的n行表示n個多米諾骨牌的點數。每行有兩個用空格隔開的正整數,表示多米諾骨牌上下方塊中的點數a和b,且1≤a,b≤6。
輸出格式:
輸出檔案僅一行,包含一個整數。表示求得的最小旋轉次數。
輸入輸出樣例
輸入樣例#1:
4
6 1
1 5
1 3
1 2
輸出樣例#1:
1
題解
DP或者背包(我寫的是背包)
代碼(Pascal)
var n,tot,x,y:longint;
a,b:array[-..]of longint;
q:array[-..]of longint;
function min(a,b:longint):longint;
begin
if a>b then exit(b) else exit(a);
end;
procedure init;
var i:longint;
begin
readln(n);
for i:= to n do
begin
read(x,y);
q[i]:=x-y;
tot:=tot+q[i];
end;
x:=*n;y:=-x;
if tot= then begin writeln();halt;end;
end;
procedure main;
var i,j:longint;
begin
for i:= to n do
begin
b:=a;
for j:=y to x do
if a[j]> then
if b[j-*q[i]]> then b[j-*q[i]]:=min(b[j-*q[i]],a[j]+)
else b[j-*q[i]]:=a[j]+;
b[-*q[i]]:=;
a:=b;
end;
i:=-tot;j:=i;
while true do
begin
if (a[i]>)and(a[i]<=a[j]) then
begin
writeln(a[i]);
halt;
end;
if a[j]> then begin writeln(a[j]);halt;end;
dec(i);inc(j);
end;
end;
begin
init;
main;
end.