Main » 2012 November 1 » 多米诺骨牌
4:50 PM 多米诺骨牌 | |
【问题描述】 多米诺骨牌有上下2个方块组成，每个方块中有1~6个点。现有排成行的n个多米诺骨牌如图8-1所示。  对于图8-1中的例子，只要将最后一个多米诺骨牌旋转180°，可使上下2行点数之差为0。 【输入】 输入文件的第一行是一个正整数n(1≤n≤1000)，表示多米诺骨牌数。接下来的n行表示n个多米诺骨牌的点数。每行有两个用空格隔开的正整数，表示多米诺骨牌上下方块中的点数a和b，且1≤a，b≤6。 【输出】 输出文件仅一行，包含一个整数。表示求得的最小旋转次数。 【样例】 dom.in 4 6 1 1 5 1 3 1 2 dom.out 1 题解： 本题是一个简单的背包型动态规划。背包型动态规划是一件物品要或不要，而在这里头是，该骨牌是否翻转。。故转移方程为q[i][j]=min(q[i-1][j-w[i][0]],q[i-1][j-w[i][1]]+1); q[i][j]表示前i个骨牌上面的数字之和为j的最小翻转次数。。w[i][0]，w[i][1]表示i骨牌上下的数字。。很简单。要想剪枝的话。可以开一个记录前i个骨牌数字和的数组。每回枚举在0~sum[i]之间。。。 代码： C++语言:made by PaulInsider!
#include #include #include using namespace std; int n,w[1005][2]={0},ssum=0,answer,ans=9999999; int q[1005][6005],sum[1005]={0}; int abs(int x) { if (x>=0) return x; else return 0-x; } int main() { freopen ("dom.in","r",stdin); freopen ("dom.out","w",stdout); cin>>n; for (int i=1;i<=n;i++) { cin>>w[i][0]>>w[i][1]; sum[i]=sum[i-1]+max(w[i][0],w[i][1]); ssum+=(w[i][0]+w[i][1]); } for (int i=0;i<=n;i++) { for (int j=0;j<=ssum;j++) { q[i][j]=99999; } } q[0][0]=0; for (int i=1;i<=n;i++) { for (int j=sum[i];j>=0;j--) { if (j-w[i][0]>=0&&q[i-1][j-w[i][0]]<q[i][j]) { q[i][j]=q[i-1][j-w[i][0]]; } if (j-w[i][1]>=0&&q[i-1][j-w[i][1]]+1<q[i][j]) { q[i][j]=q[i-1][j-w[i][1]]+1; } if (i==n) { if (abs(ssum-j*2)<ans&&q[i][j]!=99999) { ans=abs(ssum-j*2); answer=q[i][j]; } } } } cout<<answer<<endl; return 0; } | |
|
| |
| Total comments: 0 | |