《动态规划试题》由会员分享，可在线阅读，更多相关《动态规划试题（10页珍藏版）》请在金锄头文库上搜索。
1、能量项链能量项链本题是一道很经典的 dp 题目，其实质就是“石子合并问题”的变形，有谈不上什么变形，倒不如说复制更好一点。我想很多的牛人在这个题目失分的原因多为没弄懂题目的意思就下手做了，把题目看简单了。简单的说：给你一项链，项链上有 n 颗珠子。相邻的两颗珠子可以合并(两个合并成一个)。合并的同时会放出一定的能量。不同的珠子的合并所释放的能量是不同的。问：按照怎样的次序合并才能使释放的能量最多？我们用 top 表示第 i 颗珠子的头标记，用 wei 表示第 i 颗珠子的尾标记，合并两颗相邻珠子所释放的能量是：Q=top*wei*weii+1或 top*topi+1*weii+1; （一个样的
2、）合并不一定按顺序的，本题所提供的样例也是导致出错的一大原因。n 个珠子进行一次合并的后，就归结到了 n-1 个珠子的合并的问题。所以我们想到了动态规划。既然是 dp 题目，必然要满足 dp 的两大条件：、1.最优子结构性质；设 Qi,j表示第 i 颗珠子到第 j 颗珠子合并所产生的能量。显然 Q1,n表示的是合并产生的总的能量。给定一种标号方法，maxQ1,n就是所要求的。设最后一次合并在 k 处进行，则有 Q1,nQ1,kQk+1,ntop1*weik*wein。要 Q1,n最大，必然要 Q1,k，Qk+1,n最大。证明：假设 Q1,k不是最大，则必然存在一 Q1,kQ1,k。那么就有 Q
3、1,nQ1,kQk+1,ntop1*weik*weinQ1,k。这与 Q1,n的最优性矛盾。最优子结构性质得证。2.无后效性；无后效性是显然的，进行某次合并，合并前与合并后状态是相对独立，不相关联，互不影响的。算法已经定了下来了，关键是怎么实现了。项链是一个环，而我们处理是对一个串进行的。所以我们要把项链从某处割断展开，不同处的割断对应着不同的展开方法，也就是对应着不同的标号方法。产生的 maxQ1,n也就不同的。所以我们要对这些maxQ1,n进行打擂，取其最大的一个，即为解了。dp 的转移方程是：Best=maxQ1,n 1m then break;for k:=i to j-1 doif
4、fi,j0then beginwith wgqx dobeginu:=u+1;v:=vx; p:=px;end;end;for i:=1 to k dowith w dobeginfor j:=0 to 2 do write(,vj,pj,) );writeln;end;end;procedure doit;vari,j:integer;beginfillchar(f,sizeof(f),0);for i:=1 to k dowith w dobeginfor j:=1 to n dobeginfi,j:=fi-1,j;if (j=v0) and (fi,j=v0+v1) and (fi,j=
5、v0+v2) and (fi,j=v0+v1+v2) and (fi,jfi-1,j-v0-v1-v2+v0*p0+v1*p1+v2*p2)then fi,j:=fi-1,j-v0-v1-v2+v0*p0+v1*p1+v2*p2;end;end;end;procedure print;beginwriteln(fk,n);end;begininit;doit;print;end.作业调度方案作业调度方案对本题的评价：题目超长，超简单，失分率最高。当我在考场上拿到这个题目的时候，考试的紧张的气氛压抑着读了一遍，不知所云，又读了一遍，依然莫名其妙，读第三便，I give up !考试回来，一看，这
6、样的题目竟然不会，一定是气的死去活来，我就是这样郁闷了整整的一个月的。超简单的贪心算法。简单的说：有 n 个工件要在 m 个机器上加工，每个工件都有 m 到工序，每个工序对应着相应的加工机器。一个工件的工序必须依次进行。同一台机器同时只能加工一个工件。每个工件的每个工序需要一定的加工时间。问：加工完所有的工件需要的最少时间是多少？本题在题目中连算法都给出了，考察的是对题意的理解和数据结构，但本题的规模并没有对数据结构做过高的要求。应该可以说是本次考试的最简单的题目了，但不是送分题，很多人和我一样都望而止步了。最简单，按部就班就可以了。下面是题目中给我们的详尽算法：“当一个操作插入到某台机器的某
7、个空档时（机器上最后的尚未安排操作的部分也可以看作一个空档），可以靠前插入，也可以靠后或居中插入。为了使问题简单一些，我们约定：在保证约束条件（1） （2）的条件下，尽量靠前插入。并且，我们还约定，如果有多个空档可以插入，就在保证约束条件（1） （2）的条件下，插入到最前面的一个空档。 ”建议大家在考试的时候使用数组，平时可以用指针写一写（附程序） ；program Qi(input,output);varm,n:integer;a:array1.400 of integer;f:array1.20,0.1000 of boolean;wu,ti:array1.20,1.20 of integ
8、er;g,time:array1.20 of integer;procedure init;vari,j:integer;beginreadln(m,n);for i:=1 to n*m do read(a);readln;for i:=1 to n dobeginfor j:=1 to m do read(wui,j);readln;end;for i:=1 to n dobeginfor j:=1 to m do read(tii,j);readln;end;end;procedure doit;vari,j,k,xtime:integer;beginfillchar(f,sizeof(f
9、),true);fillchar(time,sizeof(time),0);fillchar(g,sizeof(g),0);for i:=1 to n*m dobegininc(ga); j:=timea+1;xtime:=0;while xtimetia,ga dobeginif fwua,ga,jthen inc(xtime)else xtime:=0;j:=j+1;end;timea:=j-1;for k:=j-xtime to j-1 do fwua,ga,k:=false;end;end;procedure print;vari,j,best:integer;beginbest:=0
10、;for i:=1 to m dofor j:=1000 downto 0 doif not fi,j thenbeginif bestj then best:=j;break;end;writeln(best);end;begininit;doit;print;end.备注：不知道为什么第 6 个数据我的答案是 112.而提供的答案是 116.?如果有错.欢迎牛人指出.呵呵.(我的 qq:418539455);备注：2k 进制数进制数这就是传说中的数学题吗?考试前曾沸沸扬扬的流传过这么一段：“今年的题目出于一数学教授，都是写超难的题目，四个题目有三个是数学题。 ”再加上今年的 maths 库
11、函数登上历史舞台。更让人深信不移：今年要考数学题。谣言不可信啊，冤死了多少牛们说本题是数学题，到不如说是个找规律的题目。我们还是用标准的数学方法做一下好了。本题其实就是个很简单的组合数学问题。没上过高三做不出也就算了，上过高三的牛们没做出来，多为放弃的了。从题中可以看出，w 的值限制着首位的取值。所以我们要对与特殊考虑。比如样例中的 w=7，就限制了首位只能取和。下面关心的就是位数的问题了，w 决定了数的最大的位数，最少的位数要求是位。k 决定了数的位权。抽象的是说了半天也不说不清楚，举个例子吧：就拿样例说，k=3。所以位权是 2k=8，w=7，决定了数的位数最大是w div k+1 ，最多位
12、的数是最高位最大只能是2(w+1) mod k-1)-1 。所以我们分两种做讨论：1.位数是最多位，2.位数小于最多位。1.位数为最多位（最多位为） ；最高位位：后面的两位只能在之间取两个不同的数。显然取法的种数为 c2,6。cn,m=m!/(n!*(m-n)!)，就是组合数 这里的最高位只能为，所以只讨论一种情况 。2.位数小于最多位。位：这两位只能从之间取数，为 c2,7。 这里只有两位的情况，所以只讨论这一种情况 。从上面的例子，我们可以看出一般的情况：位权：n=2k。 位数：l=w div k+1;当 w mod k=0 时，最高为最大为，结合下最高位最大值：2(w+1) mod k-
13、1)-1。这是我们要知道的几个基本的元素下面就是统计满足的数的个数：1.位数为最多：最高为取值 x (2=x=mhigh);对于给定最高位 x 都有一些 L 位满足条件的数，这些数的个数为 cl-1,n-x-1。：位数小于最多：对于每一个给定的 w 位数都对应着 cw,n-1个满足条件的数。把这些数的个数全部加起来就可以了。为了简化算法，我们引进一个组合公式：cn,m=cn-1,m-1+cn,m-1; 其中 cn,m=m!/(n!*(m-n)!如果不用高精度，int64 可以过个点，高精度就可以全过了。(附程序);program Qi(input,output);vark,w,n,l,mhig
14、h:integer;answer:array1.200 of integer;c:array1.512,1.512,1.100 of integer;procedure init;beginreadln(k,w);end;procedure ready;vari,j,l,jin,s:integer;beginfor i:=1 to 512 do c1,i,1:=i;for i:=2 to 512 dobeginfor j:=2 to i dobeginjin:=0;for l:=1 to 100 dobegins:=cj-1,i-1,l+cj,i-1,l+jin;cj,i,l:=s mod 1
15、0;jin:=s div 10;end;end;end;end;procedure plus(n,m:integer);vari,jin,s:integer;beginjin:=0;for i:=1 to 100 dobegins:=answer+cn,m,i+jin;jin:=s div 10;answer:=s mod 10;end;end;procedure doit;vari:integer;beginready;n:=1;for i:=1 to k do n:=n*2;n:=n-1;l:=w div k+1;mhigh:=1;for i:=1 to (w+1) mod k-1 do mhigh:=mhigh*2;mhigh:=mhigh-1;for i:=2 to l-1 do if i=n then plus(i,n);for i:=1 to mhigh do if l-1=n-i then plus(l-1,n-i);end;procedure print;vari,j:integer;beginj:=100;while answerj
