动态规划 中国骨牌 矩阵连乘 动态规划

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

编程用最少的旋转次数使多米诺骨牌上下2行点数之差达到最小。
对于图8-1中的例子,只要将最后一个多米诺骨牌旋转180°,可使上下2行点数之差为0。
【输入】
输入文件的第一行是一个正整数n(1≤n≤1000),表示多米诺骨牌数。接下来的n行表示n个多米诺骨牌的点数。每行有两个用空格隔开的正整数,表示多米诺骨牌上下方块中的点数a和b,且1≤a,b≤6。
【输出】
输出文件仅一行,包含一个整数。表示求得的最小旋转次数。
【样例输入】
4
6 1
1 5
【动态规划】中国骨牌 矩阵连乘 动态规划
1 3
1 2
【样例输出】
1

时间限制 Time Limitation
各个测试点1s


======================================================题目分析:一眼看上去,像是个背包。实际上,也确实是背包,而且是01背包。但是一不留神就会错误。以下总结几个易错点。易错点一:没有考虑到负数情况,保留状态时按差值的绝对值保留,然而这样在0附近时易出错,因为是01背包,枚举时必须保证单调性。解决方法,用一个maxf表示差值中负值的绝对值之和是多少。记录时f[i]统一记录成f[i+maxf],这样就不会出错。易错点二:更新最小值时,不更新比当前已记录最小值更大的值。这样是错误的。如果是这样写,相当于一个贪心。而实际上如果不翻转时差值是2,翻转第一块能变成4,在翻转第一块的基础上翻转第二块能使差值变成0,这样的数据如果用贪心就不会是最优解(最后记录的最优值会是2)。易错点三:for循环时应该考虑正负数,循环顺序是不同的。因为要保证是01背包,循环顺序不能错。=================================================================================我的程序:#include<stdio.h>#include<stdlib.h>inti,j,k,f[12001]={0},a[1001],n,maxz=0,maxf=0,now=0;//maxf记录负数的绝对值之和,now表示不翻转的差值,a[i]表示第i块骨牌上下点数之差,f[i]表示达到差值为i-maxf的状态所需的最小步数int main(){ scanf("%d",&n); for(i=0;i<n;i++) { scanf("%d%d",&j,&k); a[i]=j-k; if (a[i]<0) maxf-=a[i]; else maxz+=a[i]; now+=a[i]; } f[now+maxf]=1;//这里先将最小步数统一加上一,方便判断这个状态是否达到过 for(i=0;i<n;i++) if(a[i]>0) //分情况讨论,正负值的枚举状态方向相反,重要! { for(j=2*a[i];j<=maxz+maxf;j++) if(f[j]>0&&(f[j-2*a[i]]==0||f[j-2*a[i]]>f[j]+1)) f[j-2*a[i]]=f[j]+1;//如果上个状态可以达到,并且满足递推关系(以前不能达到本状态,或以前达到本状态的的最小步数小雨上个状态最小步数+1),则更新f[f-2*a[i]]。注意翻转一次是改变2*a[i]的差值。 } elseif (a[i]<0) { for(j=maxz+maxf+2*a[i];j>=0;j--) if(f[j]>0&&(f[j-2*a[i]]==0||f[j-2*a[i]]>f[j]+1))//同上 f[j-2*a[i]]=f[j]+1; } i=maxf; j=maxf; while(f[i]==0&&f[j]==0)//从差值为0开始找,同时向两边扩展,直到达到一个可以达到的状态,这个状态就是最优状态(最小差值) { i++; j--; } if (f[i]==0)printf("%dn",f[j]-1); //因为之前统一加上了一,所以要减一输出 elseif (f[j]==0||f[i]<=f[j])printf("%dn",f[i]-1); system("pause");}

  

爱华网本文地址 » http://www.aihuau.com/a/25101010/34644.html

更多阅读

关于杨澜国籍的问题引发的一些问题 杨澜是美国国籍吗

网上有微薄称人大代表杨澜是美国国籍,网民们愤愤不平,一个美国人怎么能做中国的人大代表呢,于是,在热传几天之后当事人杨澜终于站出来声明她的国籍是中国了,连百度也修改了原先的信息。在此,因为信息的不对称,我们不能查证杨澜声明的真伪的

叶荫聪:谈香港反国民教育科运动——给中国大陆青年的一封信

(作者叶荫聪系香港岭南大学文化研究系讲师,香港独立媒体的创办者)你们好!我虽住在香港,但也经常到国內跟朋友碰面,或观光购物;因为在大学教书,所以也曾在大陆做点研究或开会。几年前开始,我透过微博跟大陆的朋友聊天,围观各种大事。然而,近几个

三年级下册数学应用题88道 三年级下册连乘应用题

1.39个同学在操场上跳绳,每3人一组,可以分成多少组?2.4棵杨树苗48元,3棵松树苗63元,哪种树苗每棵的价钱贵一些?3.三(1)班小朋友做玩具,一共做了48个,送给幼儿园15个,其余的平均分给一年级3个班,每班可以分得几个?4.张教师带100元去商场买3个小足球,找

中国最贵的手机 短信接口哪家好

一款手机的价格可以在一般城市购买两套40多万元的三室两厅商品房、可以在车展上至少开回一辆凯迪拉克……这绝对不是在耸人听闻,豪华手机代言品牌Vertu就曾于2009年在长沙新世界百货专柜展出的一款白金全钻完美版手机,零售价高达880000元,

2014年世界女排锦标赛中国女排战绩 2016世界女排锦标赛

2014年世界女排锦标赛中国女排战绩出征2014年世界锦标赛中国女排全家福截止2014年10月5日,中国女排在参加世界女排锦标赛的8场比赛中获得全胜,顺利进入6强。愿中国女排取得更好的成绩。下面请看中国女排8连胜战绩。

声明:《动态规划 中国骨牌 矩阵连乘 动态规划》为网友摘嗰蘋淉分享!如侵犯到您的合法权益请联系我们删除