动态规划练习题及解答1

[题1] 多米诺骨牌（DOMINO）

问题描述：有一种多米诺骨牌是平面的，其正面被分成上下两部分，每一部分的表面或者为空，或者被标上1至6个点。现有一行排列在桌面上：

顶行骨牌的点数之和为6+1+1+1=9；底行骨牌点数之和为1+5+3+2=11。顶行和底行的差值是2。这个差值是两行点数之和的差的绝对值。每个多米诺骨牌都可以上下倒置转换，即上部变为下部，下部变为上部。

现在的任务是，以最少的翻转次数，使得顶行和底行之间的差值最小。对于上面这个例子，我们只需翻转最后一个骨牌，就可以使得顶行和底行的差值为0，所以例子的答案为1。 输入格式：

文件的第一行是一个整数n（1〈=n〈=1000〉，表示有n个多米诺骨牌在桌面上排成一行。接下来共有n行，每行包含两个整数a、b（0〈=a、b〈=6，中间用空格分开〉。第I+1行的a、b分别表示第I个多米诺骨牌的上部与下部的点数（0表示空）。 输出格式：

只有一个整数在文件的第一行。这个整数表示翻动骨牌的最少次数，从而使得顶行和底行的差值最小。

[题2] Perform巡回演出 题目描述:

Flute市的Phlharmoniker乐团2000年准备到Harp市做一次大型演出,本着普及古典音乐的目的,乐团指挥L.Y.M准备在到达Harp市之前先在周围一些小城市作一段时间的巡回演出,此后的几天里,音乐家们将每天搭乘一个航班从一个城市飞到另一个城市,最后才到达目的地Harp市(乐团可多次在同一城市演出).

由于航线的费用和班次每天都在变,城市和城市之间都有一份循环的航班表,每一时间,每一方向,航班表循环的周期都可能不同.现要求寻找一张花费费用最小的演出表.

输入: 输入文件包括若干个场景.每个场景的描述由一对整数n(2<=n<=10)和k(1<=k<=1000)开始,音乐家们要在这n个城市作巡回演出,城市用1..n标号,其中1是起点Flute市,n是终点Harp市,接下来有n*(n-1)份航班表,一份航班表一行,描述每对城市之间的航线和价格,第一组n-1份航班表对应从城市1到其他城市(2,3,...n)的航班,接下的n-1行是从城市2到其他城市(1,3,4...n)的航班,如此下去. 每份航班又一个整数d(1<=d<=30)开始,表示航班表循环的周期,接下来的d个非负整数表示1,2...d天对应的两个城市的航班的价格,价格为零表示那天两个城市之间没有航班.例如\"3 75 0 80\"表示第一天机票价格是75KOI,第二天没有航班,第三天的机票是80KOI,然后循环:第四天又是75KOI,第五天没有航班,如此循环.输入文件由n=k=0的场景结束. 输出:

对每个场景如果乐团可能从城市1出发,每天都要飞往另一个城市,最后(经过k天)抵达城市n,则输出这k个航班价格之和的最小值.如果不可能存在这样的巡回演出路线,输出0.

样例输入: 样例输出：

3 6 460 2 130 150 0 3 75 0 80

7 120 110 0 100 110 120 0 4 60 70 60 50 3 0 135 140 2 70 80 2 3 2 0 70 1 80 0 0

[题3] 复制书稿（BOOKS）

问题描述：假设有M本书（编号为1，2，„M），想将每本复制一份，M本书的页数可能不同（分别是P1，P2，„PM）。任务时将这M本书分给K个抄写员（K〈=M〉，每本书只能分配给一个抄写员进行复制，而每个抄写员所分配到的书必须是连续顺序的。

意思是说，存在一个连续升序数列0=bo〈b1〈b2〈„输入格式：

文件的第一行是两个整数m和k (1〈=k〈=m〈=500)。

第二行有m个整数P1，P2，„，Pm，这m个整数均为正整数且都不超过1000000。每两个整数之间用空格分开。 输出格式：

文件有k行，每行有两个正整数。整数之间用空格分开。

第I行的两个整数ai和bi，表示第I号抄写员所分配得到的书稿的起始编号与终止编号。

动态规划题参考程序：

题1：

解决问题：例子的上下部分之差是6+1+1+1-（1+5+3+2）=（6-1）+（1-5）+（1-3）+（1-2）=-2，而翻转最后一个骨牌后，上下之差变为（6-1）+（1-5）+（1-3）+（2-1）=0。由此看出，一个骨牌对翻转策略造成影响的是上下两数之差，骨牌上的数则是次要的了。这么一来，便把骨牌的放置状态由8个数字变为4个： 5 -4 -2 -1，翻转时只需取该位数字的相反数就行了。

在本题中，因为各骨牌的翻转顺序没有限定，所以不能按骨牌编号作为阶段来划分。怎么办呢？考虑到隐含阶段类型的问题可以按状态最优值的大小来划分阶段。于是，我们以骨牌序列上下两部分的差值I作为状态，把达到这一状态的翻转步数作为状态值，记为f（I）。便有f（I）=min{f（I+j）+1} （-12〈=j<=12,j为偶数，且要求当前状态有差值为j/2的骨牌）。这里，I不是无限增大或减小，其范围取决于初始骨牌序列的数字差的和的大小。

具体动态规划时，如例题，我们以f（-2）=0起步，根据骨牌状态，进行一次翻转，可得到f（-12）=1，f（6）=1，f（2）=1，f（0）=1，由于出现了f（0），因此程序便可以结束，否则将根据四个新状态继续扩展，直至出现f（0）或者无法生成新状态为止。

注意：在各状态，除记录最少步数外，还需记录到达这一状态时各骨牌的放置情况；而当到达某一状态发现已记录有一种翻转策略时，则取步数较小的一种。 程序如下：

program domino;

type tp=array[1..6] of integer; var t:array[1..6000] of ^tp; {记录骨牌摆放状态}

f:array[-6000..6000] of integer; {记录达到某个差值的最少步数} l:array[1..6000] of integer; {扩展队列} tt:tp;

i,j,n,m,x,y,ft,re:integer; f1,f2:text; procedure init; {程序初始化} begin

assign(f1,'domino.dat'); reset(f1);

assign(f2,'domino.out'); rewrite(f2); m:=0;

ft:=0;re:=1;new(t[1]);

fillchar(t[1]^,sizeof(t[1]^),0); fillchar(f,sizeof(f),0); fillchar(tt,sizeof(tt),0); readln(f1,n); for i:=1 to n do begin

readln(f1,x,y); if x<>y then

begin x:=x-y; inc(m,x);

inc(tt[abs(x)]);

if x>0 then inc(t[1]^[x]); end; end;

if m=0 then begin

writeln(f2,0); close(f2); halt; end;

{处理步数为零的情况} l[1]:=m; f[m]:=1; end;

procedure main; {主过程} begin repeat

for ft:=ft+1 to re do {以步数为阶段扩展状态} begin

x:=l[ft];

for i:=1 to 6 do {不同差值的六种情况} begin

if x<6 then

if (t[ft]^[i]inc(re);l[re]:=x+i*2; f[l[re]]:=f[x]+1; if l[re]=0 then {找到解便打印} begin

writeln(f2,f[l[re]]-1); close(f2); halt; end;

new(t[re]); t[re]^:=t[ft]^; inc(t[re]^[i]); end;

{差值增加} if x>-6 then

if (t[ft]^[i]>0)and(f[x-i*2]=0) then begin

inc(re);l[re]:=x-i*2; f[l[re]]:=f[x]+1; if l[re]=0 then

{找到解便打印} begin

writeln(f2,f[l[re]]-1); close(f2); halt; end;

new(t[re]); t[re]^:=t[ft]^; dec(t[re]^[i]); end;

{差值减少} end; end;

until ft=re; for i:=1 to 6 do

if (f[i]>0)or(f[-i]>0) then begin

if (f[-i]>0)and((f[i]=0)or(f[-i]close(f2);

{骨牌上下两行点数之和的绝对值不为零} end; begin init; main; end.

题2：

初看这道题,很容易便可以想到动态规划,因为第x天在第y个地方的最优值只与第x-1天有关,符合动态规划的无后效性原则,即只与上一个状态相关联,而某一天x航班价格不难求出S=C[(x-1) mod m +1].我们用天数和地点来规划用一个数组A[1..1000,1..10]来存储,A[i,j]表示第i天到达第j个城市的最优值,C[i,j,l]表示i城市与j城市间第l天航班价格,则A[i,j]=Min{A[i-1,l]+C[l,j,i] (l=1..n且C[l,j,i]<>0)},动态规划方程一出,尽可以放怀大笑了. 示范程序:

program perform_hh; var

f,fout:text;

p,l,i,j,n,k:integer;

a:array [1..1000,1..10] of integer; {动态规划数组} c:array [1..10,1..10] of record {航班价格数组} num:integer;

t:array [1..30] of integer; end; e:array [1..1000] of integer; procedure work;

begin

{人工赋第一天各城市最优值} for i:=1 to n do begin

if c[1,i].t[1]<>0

then a[1,i]:=c[1,i].t[1]; end;

for i:=2 to k do begin

for j:=1 to n do begin

for l:=1 to n do begin if (j<>l)

and (c[l,j].t[(i-1) mod c[l,j].num+1]<>0) {判断存在航班}

and ((a[i,j]=0) or (a[i-1,l]+c[l,j].t[(i-1) mod c[l,j].num+1]then a[i,j]:=a[i-1,l]+c[l,j].t[(i-1) mod c[l,j].num+1]; {赋值} end; end; end;

e[p]:=a[k,n]; {第p个场景的最优值} end;

procedure readfile; {读文件} begin

assign(f,'PERFORM.DAT'); reset(f);

assign(fout,'PERFORM.OUT'); rewrite(fout); readln(f,n,k); p:=0;

while (n<>0) and (k<>0) do begin p:=p+1;

fillchar(c,sizeof(c),0); fillchar(a,sizeof(a),0); for i:=1 to n do begin

for j:=1 to i-1 do begin

read(f,c[i,j].num);

for l:=1 to c[i,j].num do read(f,c[i,j].t[l]); end;

for j:=i+1 to n do begin

read(f,c[i,j].num);

for l:=1 to c[i,j].num do read(f,c[i,j].t[l]); end; end; work;

readln(f,n,k); end;

{输出各个场景的解} for i:=1 to p-1 do writeln(fout,e[i]); write(fout,e[p]); close(f); close(fout); end; begin

readfile; end. [题3：]

解决问题：该题中M本书是顺序排列的，K个抄写员选择数也是顺序且连续的。不管以书的编号，还是以抄写员标号作为参变量划分阶段，都符合策略的最优化原理和无后效性。考虑到K〈=M，以抄写员编号来划分会方便些。

设F（I，J）为前I个抄写员复制前J本书的最小“页数最大数”。于是便有F（I，J）=MIN{ F（I-1，V），T（V+1，J）} （1〈=I〈=K，I〈=J〈=M-K+I，I-1〈=V〈=J-1〉。 其中T（V+1，J）表示从第V+1本书到第J本书的页数和。起步时F（1，1）=P1。

观察函数递推式，发现F（I）阶段只依赖于F（I-1）阶段的状态值，编程时可令数组F的范围为（0„1,1„M），便于缩小空间复杂度。 程序如下：

program books;

type tp=array[1..500] of integer; tc=array[1..500] of longint; var c:array[1..500] of ^tp; {记录路径}

f:array[0..1] of tc; {状态值} t:tc;

{书本页数和} cc:tp; {链接路径}

i,j,v,k,m,x,y,min,p1,p2:longint; f1,f2:text; procedure init; {输入部分} begin

assign(f1,'books.dat'); reset(f1);

assign(f2,'books.out'); rewrite(f2); readln(f1,m,k); if k=1 then begin

writeln(f2,1,' ',m); close(f2);

halt; end;

{当k=1时,作特殊处理} for i:=1 to m do begin

read(f1,j);

if i=1 then t[1]:=j else t[i]:=t[i-1]+j; {累加页数} end;

for i:=1 to k do new(c[i]); end;

procedure main; {主过程} begin

p1:=1;f[1]:=t; {起步状态}

for i:=2 to k-1 do {利用函数递推式计算} begin

p2:=p1;p1:=1-p2; for j:=i to m-k+i do begin

min:=maxlongint;y:=0; for v:=i-1 to j-1 do begin

if f[p2,v]>t[j]-t[v] then x:=f[p2,v] else x:=t[j]-t[v]; if xf[p1,j]:=min; c[i]^[j]:=y; end; end;

p2:=p1;p1:=1-p2;

min:=maxlongint;y:=0; for i:=k-1 to m-1 do begin

if f[p2,i]>t[m]-t[i] then x:=f[p2,i] else x:=t[m]-t[i]; if x{最后找出最优分配方案} for i:=k-1 downto 1 do begin

cc[i]:=y; y:=c[i]^[y]; end;

{链接路径}

writeln(f2,1,' ',cc[1]); for j:=2 to k-1 do

writeln(f2,cc[j-1]+1,' ',cc[j]);

writeln(f2,cc[k-1]+1,' ',m); close(f2); {打印} end; begin init; main; end.