題目描述

多米諾骨牌有上下2個方塊組成，每個方塊中有1~6個點。現(xiàn)有排成行的

上方塊中點數(shù)之和記為S1，下方塊中點數(shù)之和記為S2，它們的差為|S1-S2|。例如在圖8-1中，S1=6+1+1+1=9，S2=1+5+3+2=11，|S1-S2|=2。每個多米諾骨牌可以旋轉180°，使得上下兩個方塊互換位置。 編程用最少的旋轉次數(shù)使多米諾骨牌上下2行點數(shù)之差達到最小。

對于圖中的例子，只要將最后一個多米諾骨牌旋轉180°，可使上下2行點數(shù)之差為0。

輸入輸出格式

輸入格式：

?

輸入文件的第一行是一個正整數(shù)n(1≤n≤1000)，表示多米諾骨牌數(shù)。接下來的n行表示n個多米諾骨牌的點數(shù)。每行有兩個用空格隔開的正整數(shù)，表示多米諾骨牌上下方塊中的點數(shù)a和b，且1≤a，b≤6。

?

輸出格式：

?

輸出文件僅一行，包含一個整數(shù)。表示求得的最小旋轉次數(shù)。

?

輸入輸出樣例

輸入樣例#1： 4 6 1 1 5 1 3 1 2 輸出樣例#1:

1

Solution

此題是一道雙向背包.

這道題一看,就覺得應該和背包有點關系.然后要想到背包的本質是什么.

背包的本質就是通過當前狀態(tài)的前驅, 進行更新.

然后就是狀態(tài)定義:

f[ i ][ j ] 表示 前 i 個組合里面 上面那個數(shù)組的和.?

同時因為無論怎么變化 兩個數(shù)列的總和始終是不變的.

所以之后的狀態(tài)轉移方程和 背包非常相似.

可以試著自己想一想.

?

Ps: 注意 f[1][ ] 的初始化.

?

代碼(內(nèi)有一部分注釋) :

#include<bits/stdc++.h> using namespace std; const int maxn=1008; const int inf=1231654;int n,a[maxn],b[maxn];int w[maxn],sum;int f[maxn][6*maxn];//狀態(tài)表示 前 i 個里面上一列的值是多少.//同時因為交換不會改變兩列數(shù)的總和,所以可以很方便地求出另外一列的值 int main() {scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d%d",&a[i],&b[i]);sum+=(a[i]+b[i]);}//表示 初始狀態(tài). 若第一個換就是 0 否則為1;for(int i=1;i<=n;i++)for(int j=0;j<=n*6+10;j++) f[i][j]=inf;f[1][a[1]]=0; f[1][b[1]]=1;for(int i=2;i<=n;i++)// 注意從 2 開始for(int j=0;j<=n*6;j++){if(j-a[i]>=0)f[i][j]=min(f[i][j], f[i-1][j-a[i]]);//若仍然為a 則不需要去加;if(j-b[i]>=0)f[i][j]=min(f[i][j], f[i-1][j-b[i]]+1);}int minc=inf,mint=inf;for(int i=1;i<=sum;i++){if(f[n][i]!=inf)if(abs(i-(sum-i))<minc)minc=abs(i-(sum-i)),mint=f[n][i];elseif(abs(i-(sum-i))==minc) mint=min(f[n][i],mint);}cout<<mint<<endl;return 0; }

?

?

轉載于:https://www.cnblogs.com/Kv-Stalin/p/8708825.html

總結

以上是生活随笔為你收集整理的P1282 多米诺骨牌 (差值DP+背包)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。