Main » 2012 » November » 1 » 多米诺骨牌
4:50 PM
多米诺骨牌

【问题描述】

多米诺骨牌有上下2个方块组成,每个方块中有1~6个点。现有排成行的n个多米诺骨牌如图8-1所示。

编程用最少的旋转次数使多米诺骨牌上下2行点数之差达到最小。上方块中点数之和记为sum1,下方块中点数之和记为sum2,它们的差为|sum1-sum2|。例如在图8-1中,sum1=6+1+1+1=9,sum2=1+5+3+2=11,|sum1-sum2|=2。每个多米诺骨牌可以旋转180°,使得上下两个方块互换位置。

对于图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

题解:

本题是一个简单的背包型动态规划。背包型动态规划是一件物品要或不要,而在这里头是,该骨牌是否翻转。。故转移方程为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 <iostream>
#include <cstdio>
#include <cstdlib>
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;
}


Views: 629 | Added by: dandan | Tags: NOIP | Rating: 0.0/0
Total comments: 0
Name *:
Email *:
Code *: