第一章 什么叫动态规划

1.1 多阶段决策过程的最优化问题

1、问题的提出

首先，例举一个典型的且很直观的多阶段决策问题:

[例] 下图表示城市之间的交通路网，线段上的数字表示费用，单向通行由A->E。求A->E的最省费用。

如图从A到E共分为4个阶段，即第一阶段从A到B，第二阶段从B到C，第三阶段从C到D，第四阶段从D到E。除起点A和终点E外，其它各点既是上一阶段的终点又是下一阶段的起点。例如从A到B的第一阶段中，A为起点，终点有B1，B2，B3三个，因而这时走的路线有三个选择，一是走到B1，一是走到B2，一是走到B3。若选择B2的决策，B2就是第一阶段在我们决策之下的结果，它既是第一阶段路线的终点，又是第二阶段路线的始点。在第二阶段，再从B2点出发，对于B2点就有一个可供选择的终点集合(C1，C2，C3)；若选择由B2走至C2为第二阶段的决策，则C2就是第二阶段的终点，同时又是第三阶段的始点。同理递推下去，可看到各个阶段的决策不同，线路就不同。很明显，当某阶段的起点给定时，它直接影响着后面各阶段的行进路线和整个路线的长短，而后面各阶段的路线的发展不受这点以前各阶段的影响。故此问题的要求是：在各个阶段选取一个恰当的决策，使由这些决策组成的一个决策序列所决定的一条路线，其总路程最短。具体情况如下：

（1）由目标状态E向前推，可以分成四个阶段，即四个子问题。如上图所示。

（2）策略：每个阶段到E的最省费用为本阶段的决策路径。

（3）D1，D2是第一次输人的结点。他们到E都只有一种费用，在D1框上面标5，D2框上面标2。目前无法定下，那一个点将在全程最优策略的路径上。第二阶段计算中，5，2都应分别参加计算。

（4）C1，C2，C3是第二次输入结点，他们到D1，D2各有两种费用。此时应计算C1，C2，C3分别到E的最少费用。

C1的决策路径是 min{（C1D1），（C1D2）}。计算结果是C1+D1+E，在C1框上面标为8。

同理C2的决策路径计算结果是C2+D2+E，在C2框上面标为7。

同理C3的决策路径计算结果是C3+D2+E，在C3框上面标为12。

此时也无法定下第一，二阶段的城市那二个将在整体的最优决策路径上。

（5）第三次输入结点为B1，B2，B3，而决策输出结点可能为C1，C2，C3。仿前计算可得Bl，B2，B3的决策路径为如下情况。

Bl:B1C1费用 12+8=20， 路径:B1+C1+D1+E

B2:B2C1费用 6+8=14， 路径:B2+C1+D1+E

B3:B2C2费用 12+7=19， 路径:B3+C2+D2+E

此时也无法定下第一，二，三阶段的城市那三个将在整体的最优决策路径上。

（6）第四次输入结点为A，决策输出结点可能为B1，B2，B3。同理可得决策路径为

A：AB2，费用5+14=19，路径 A+B2+C1+D1+E。

此时才正式确定每个子问题的结点中，那一个结点将在最优费用的路径上。19将结果显然这种计算方法，符合最优原理。子问题的决策中，只对同一城市（结点）比较优劣。而同一阶段的城市（结点）的优劣要由下一个阶段去决定。

1.2 动态规划的概念

在上例的多阶段决策问题中，各个阶段采取的决策，一般来说是与时间有关的，决策依赖于当前状态，又随即引起状态的转移，一个决策序列就是在变化的状态中产生出来的，故有“动态”的含义，称这种解决多阶段决策最优化问题的方法为动态规划方法。

与穷举法相比，动态规划的方法有两个明显的优点:

(1)大大减少了计算量

(2)丰富了计算结果

从上例的求解结果中，我们不仅得到由A点出发到终点E的最短路线及最短距离，而且还得到了从所有各中间点到终点的最短路线及最短距离，这对许多实际问题来讲是很有用的。

动态规划的最优化概念是在一定条件下，我到一种途径，在对各阶段的效益经过按问题具体性质所确定的运算以后，使得全过程的总效益达到最优。

应用动态规划要注意阶段的划分是关键，必须依据题意分析，寻求合理的划分阶段(子问题)方法。而每个子问题是一个比原问题简单得多的优化问题。而且每个子问题的求解中，均利用它的一个后部子问题的最优化结果，直到最后一个子问题所得最优解，它就是原问题的最优解。

1.3 动态规划适合解决什么样的问题

    准确地说，动态规划不是万能的，它只适于解决一定条件的最优策略问题。

    或许，大家听到这个结论会很失望：其实，这个结论并没有削减动态规划的光辉，因为属于上面范围内的问题极多，还有许多看似不是这个范围中的问题都可以转化成这类问题。

    上面所说的“满足一定条件”主要指下面两点：

    (1)状态必须满足最优化原理；

    (2)状态必须满足无后效性。

动态规划的最优化原理是无论过去的状态和决策如何，对前面的决策所形成的当前状态而言，余下的诸决策必须构成最优策略。  可以通俗地理解为子问题的局部最优将导致整个问题的全局最优在上例中例题1最短路径问题中，A到E的最优路径上的任一点到终点E的路径也必然是该点到终点E的一条最优路径，满足最优化原理。

动态规划的无后效性原则某阶段的状态一旦确定，则此后过程的演变不再受此前各状态及决策的影响。也就是说，“未来与过去无关”，当前的状态是此前历史的一个完整总结，此前的历史只能通过当前的状态去影响过程未来的演变。具体地说，如果一个问题被划分各个阶段之后，阶段 I 中的状态只能由阶段 I+1 中的状态通过状态转移方程得来，与其他状态没有关系，特别是与未发生的状态没有关系，这就是无后效性。   　　

第二章 用动态规划法解题

2.1 为什么要用动态规划法解题

首先，看下面一个问题:

【例题1】数字三角形问题。

               7

              3 8

             8 1 0

            2 7 7 4

           5 5 2 6 5

示出了一个数字三角形宝塔。数字三角形中的数字为不超过100的正整数。现规定从最顶层走到最底层，每一步可沿左斜线向下或右斜线向下走。假设三角形行数≤100，编程求解从最顶层走到最底层的一条路径，使得沿着该路径所经过的数字的总和最大，输出最大值。输人数据：由文件输入数据，文件第一行是三角形的行数N。以后的N行分别是从最顶层到最底层的每一层中的数字。

如输入： 5

7           

3 8         

8 1 0     

2 7 7 4     

4 5 2 6 5   

输出：30

【分析】对于这一问题，很容易想到用枚举的方法（深度搜索法）去解决，即列举出所有路径并记录每一条路径所经过的数字总和。然后寻找最大的数字总和，这一想法很直观，很容易编程实现其程序如下：

program sjx;

const maxn=10;

var

a:array[1..maxn,1..maxn] of integer;

max:longint;

n,i,j:integer;

fname:string;

inputf:text;

procedure try(x,y,dep:integer;sum:longint);

begin

  if (dep=n) then

   begin

   if sum>max then  max:=sum;

    exit

   end;

  try(x+1,y,dep+1,sum+a[x+1,y]);

  try(x+1,y+1,dep+1,sum+a[x+1,y+1]);

end;

begin

 readln(fname);

 assign(inputf,fname);

 reset(inputf);

 readln(inputf,n);

 for i:=1 to n do

  for j:= 1 to i do

   read(inputf,a[i,j]);

 max:=0;

 try(1,1,1,a[1,1]);

 writeln(max);

end.

但是当行数很大时，当三角形的行数等于100时，其枚举量之大是可想而知的，用枚举法肯定超时，甚至根本不能得到计算结果，必须用动态规划法来解。

2.2 怎样用动态规划法解题

1.逆推法:

按三角形的行划分阶段，若行数为 n，则可把问题看做一个n-1个阶段的决策问题。先求出第n-1阶段(第n-1行上各点)到第n行的的最大和，再依次求出第n-2阶段、第n-3阶段……第1阶段(起始点)各决策点至第n行的最佳路径。

设：f[i,j]为从第i阶段中的点j至第n行的最大的数字和；

则: f[n,j]=a[n,j]   1<=j<=n

    f[i,j]=max{a[i,j]+f[i+1,j],a[i,j]+f[i+1,j+1]}  1<=j<=i.

    f[1,1]即为所求。

程序如下：

program datasjx;

const maxn=100;

var

 fname:string;

 inputf:text;

 n,i,j:integer;

 a:array[1..maxn,1..maxn] of integer;

 f:array[1..maxn,1..maxn] of integer;

begin

 readln(fname);

 assign(inputf,fname);

 reset(inputf);

 readln(inputf,n);

 for i:=1 to n do

  for j:=1 to i do

   read(inputf,a[i,j]);

 for i:=1 to n do

   f[n,i]:=a[n,i];

 for i:=n-1 downto 1 do

  for j:=1 to i do

   if f[i+1,j]>f[i+1,j+1] then f[i,j]:=a[i,j]+f[i+1,j]

    else f[i,j]:=a[i,j]+f[i+1,j+1];

 writeln(f[1,1]);

end.    

2. 顺推法

按三角形的行划分阶段，若行数为 n，则可把问题看做一个n-1个阶段的决策问题。先求第2行各元素到起点的最大和

,再依次求出第3,4，5,......,.n-1,n到起点的最大和,最后找第n行的最大值

设f[i,j]为 第i行第j列上点到起点的最大和

则 f[1，1]=a[1,1];

       f[i，1]=a[i, 1]+f[i-1,1];

       f[ i，j ]=max{ a[i,j]+f[i-1,j-1],a[i,j]+f[i-1,j]}    2<=j<=i

 max(f[n,1],f[n,2],.......,f[n,n]}即为所求。

程序如下：

program datasjx;

const maxn=100;

var

 fname:string;

 inputf:text;

 n,i,j:integer;

 a:array[1..maxn,1..maxn] of integer;

 f:array[1..maxn,1..maxn] of integer;

 maxsum:integer;

begin

 readln(fname);

 assign(inputf,fname);

 reset(inputf);

 readln(inputf,n);

 for i:=1 to n do

  for j:=1 to i do

   read(inputf,a[i,j]);

 fillchar(f,sizeof(f),0);

 f[1,1]:=a[1,1];

 for i:=2 to n do

  begin

  f[i,1]:=a[i,1]+f[i-1,1];

  for j:=2 to i do

   if f[i-1,j-1]>f[i-1,j] then f[i,j]:=a[i,j]+f[i-1,j-1]

    else f[i,j]:=a[i,j]+f[i-1,j];

  end;

 maxsum:=0;

 for i:=1 to n do

  if f[n,i]>maxsum then maxsum:=f[n,i];

 writeln(maxsum);

end.

说明一下：

1.用动态规划解题主要思想是用空间换时间.

2.本题如果n较大，用2维数组空间可能不够,可以使用1维数组.

程序如下:

program datasjx;

const maxn=100;

var

 fname:string;

 inputf:text;

 n,i,j:integer;

 a:array[1..maxn,1..maxn] of integer;

 f:array[1..maxn] of integer;

 maxsum:integer;

begin

 readln(fname);

 assign(inputf,fname);

 reset(inputf);

 readln(inputf,n);

 for i:=1 to n do

  for j:=1 to i do

   read(inputf,a[i,j]);

 fillchar(f,sizeof(f),0);

 f[1]:=a[1,1];

 for i:=2 to n do

  begin

  for j:=i downto 2 do

   if f[j-1]>f[j] then f[j]:=a[i,j]+f[j-1]

    else f[j]:=a[i,j]+f[j];

  f[1]:=a[i,1]+f[1];

  end;

 maxsum:=0;

 for i:=1 to n do

  if f[i]>maxsum then maxsum:=f[i];

 writeln(maxsum);

end.

练习:用一维数组和逆推法解本题.

2.3 用动态规划法解题的一般模式

动态规划所处理的问题是一个多阶段决策问题，一般由初始状态开始，通过对中间阶段决策的选择，达到结束状态。这些决策形成了一个决策序列，同时确定了完成整个过程的一条活动路线(通常是求最优的活动路线)。如图所示。动态规划的设计都有着一定的模式，一般要经历以下几个步骤。

┌───┐ ┌───┐ ┌───┐

初始状态→│决策１│→│决策２│→…→│决策ｎ│→结束状态

└───┘ └───┘ └───┘

(1)划分阶段：按照问题的时间或空间特征，把问题分为若干个阶段。在划分阶段时，注意划分后的阶段一定要是有序的或者是可排序的，否则问题就无法求解。

(2)确定状态和状态变量：将问题发展到各个阶段时所处于的各种客观情况用不同的状态表示出来。当然，状态的选择要满足无后效性。

(3)确定决策并写出状态转移方程：因为决策和状态转移有着天然的联系，状态转移就是根据上一阶段的状态和决策来导出本阶段的状态。所以如果确定了决策，状态转移方程也就可写出。但事实上常常是反过来做，根据相邻两段各状态之间的关系来确定决策。

(4)寻找边界条件：给出的状态转移方程是一个递推式，需要一个递推的终止条件或边界条件。

(5)程序设计实现：动态规划的主要难点在于理论上的设计，一旦设计完成，实现部分就会非常简单。

根据上述动态规划设计的步骤，可得到大体解题框架如下:

     1.初始化(边界条件)

     2.for i:=2 to n (顺推法)  或 for i:=n-1 to 1(逆推法)

         对i阶段的每一个决策点求局部最优

     3.确定和输出结束状态的值.             

第三章 典型例题与习题

3.1 最长不降子序列

（1）问题描述

设有由n个不相同的整数组成的数列，记为:

a(1)、a(2)、……、a(n)且a(i)<>a(j)  (i<>j)

例如3，18，7，14，10，12，23，41，16，24。

若存在i1… < ie 且有a(i1)… 则称为长度为e的不下降序列。如上例中3，18，23，24就是一个长度为4的不下降序列，同时也有3，7，10，12，16，24长度为6的不下降序列。程序要求，当原数列给出之后，求出最长的不下降序列。

（2）算法分析

根据动态规划的原理，由后往前进行搜索。

1· 对a(n)来说，由于它是最后一个数，所以当从a(n)开始查找时，只存在长度为1的不下降序列；

2· 若从a(n-1)开始查找，则存在下面的两种可能性：

①若a(n-1)则存在长度为2的不下降序列a(n-1)，a(n)。

②若a(n-1)>a(n)则存在长度为1的不下降序列a(n-1)或a(n)。

3· 一般若从a(i)开始，此时最长不下降序列应该按下列方法求出:

在a(i+1),a(i+2),…,a(n)中，找出一个比a(i)大的且最长的不下降序列，作为它的后继。

4.用数组b(i),c(i)分别记录点i到n的最长的不降子序列的长度和点i后继接点的编号

(3) 程序如下:（逆推法）

program li1;

const maxn=100;

var a,b,c:array[1..maxn] of integer;

    fname:string;

    f:text;

    n,i,j,max,p:integer;

begin

 readln(fname);

 assign(f,fname);

 reset(f);

 readln(f,n);+

 for i:=1 to n do

  begin

  read(f,a[i]);

  b[n]:=1;

  c[n]:=0;

  end;

 for i:= n-1 downto 1 do

  begin

   max:=0;p:=0;

   for j:=i+1 to n do

    if (a[i]max) then  begin max:=b[j];p:=j end;

   if p<>0 then begin b[i]:=b[p]+1;c[i]:=p end

  end;

 max:=0;p:=0;

 for i:=1 to n do

  if b[i]>max then begin max:=b[i];p:=i end;

 writeln('maxlong=',max);

 write('result is:');

 while p<>0 do

  begin write(a[p]:5);p:=c[p] end;

end.

3.2 背包问题

背包问题有三种

1.部分背包问题　

一个旅行者有一个最多能用m公斤的背包，现在有n种物品，它们的总重量分别是W1，W2，...,Wn,它们的总价值分别为C1,C2,...,Cn.求旅行者能获得最大总价值。

解决问题的方法是贪心算法:将C1/W1,C2/W2,...Cn/Wn,从大到小排序,不停地选择价值与重量比最大的放人背包直到放满为止.

2.0/1背包

一个旅行者有一个最多能用m公斤的背包，现在有n件物品，它们的重量分别是W1，W2，...,Wn,它们的价值分别为C1,C2,...,Cn.若每种物品只有一件求旅行者能获得最大总价值。

 <1>分析说明:

显然这个题可用深度优先方法对每件物品进行枚举(选或不选用0,1控制).

程序简单,但是当n的值很大的时候不能满足时间要求，时间复杂度为O（2n）。按递归的思想我们可以把问题分解为子问题,使用递归函数

设 f(i，x)表示前i件物品，总重量不超过x的最优价值

则 f（i，x）=max(f(i－1，x-W[i])+C[i]，f（i－1，x））

f（n，m）即为最优解，边界条件为f（0，x）＝0 ，f(i,0)=0;

动态规划方法(顺推法)程序如下:

程序如下：

program knapsack02;

 const maxm=200;maxn=30;

 type ar=array[1..maxn] of integer;

 var m,n,j,i:integer;

 c,w:ar;

 f:array[0..maxn,0..maxm] of integer;

 function max(x,y:integer):integer;

 begin

  if x>y then max:=x else max:=y;

 end;

 begin

  readln(m,n);

  for i:= 1 to n do

   readln(w[i],c[i]);

  for i:=1 to m do f(0,i):=0;

  for i:=1 to n do f(i,0):=0;

 for i:=1 to n do

   for j:=1 to m do

    begin

      if j>=w[i]  then f[i,j]:=max(f[i-1,j-w[i]]+c[i],f[i-1,j])

     else f[i,j]:=f[i-1,j];

    end;

  writeln(f[n,m]);

  end.

使用二维数组存储各子问题时方便，但当maxm较大时如maxn=2000时不能定义二维数组f,怎么办,其实可以用一维数组,但是上述中j:=1 to m 要改为j:=m downto 1,为什么?请大家自己解决。

3.完全背包问题

一个旅行者有一个最多能用m公斤的背包，现在有n种物品，每件的重量分别是W1，W2，...,Wn,

每件的价值分别为C1,C2,...,Cn.若的每种物品的件数足够多.

求旅行者能获得的最大总价值。

本问题的数学模型如下：

设 f(x)表示重量不超过x公斤的最大价值，

则 f(x）=max{f(x-w[i])+c[i]}  当x>=w[i] 1<=i<=n

程序如下:（顺推法）

program knapsack04;

 const maxm=2000;maxn=30;

 type ar=array[0..maxn] of integer;

 var m,n,j,i,t:integer;

 c,w:ar;

 f:array[0..maxm] of integer;

 begin

  readln(m,n);

  for i:= 1 to n do

   readln(w[i],c[i]);

   f(0):=0;

  for i:=1 to m do

   for j:=1 to n do

    begin

     if i>=w[j]  then t:=f[i-w[j]]+c[j];

       if t>f[i] then f[i]:=t

    end;

  writeln(f[m]);

  end.

3.3 最短路径

问题描述：

如图：求v1到v10的最短路径长度及最短路径。

图的邻接矩阵如下：

0 2 5 1 -1 -1 -1 -1 -1 -1

-1 0 -1 -1 12 14 -1 -1 -1 -1

-1 -1 0 -1 6 10 4 -1 -1 -1

-1 -1 -1 0 13 12 11 -1 -1 -1

-1 -1 -1 -1 0 -1 -1 3 9 -1

-1 -1 -1 -1 -1 0 -1 6 5 -1

-1 -1 -1 -1 -1 -1 0 -1 10 -1

-1 -1 -1 -1 -1 -1 -1 0 -1 5

-1 -1 -1 -1 -1 -1 -1 -1 0 2

-1 -1 -1 -1 -1 -1 -1 -1 -1 0

采用逆推法

设f（x）表示点x到v10的最短路径长度

则 f(10)=0

   f(x)=min{ f(i)+a[x,i] 当a[x,i]>0 ,x

程序如下：（逆推法）

program lt3;

const n=10;

var

 a:array[1..n,1..n] of integer;

 b,c:array[1..n] of integer;

 fname:string;

 f:text;

 i,j,x:integer;

begin

 readln(fname);

 assign(f,fname);

 reset(f);

 for i:=1 to n do

  for j:=1 to n do

   read(f,a[i,j]);

 close(f);

 for i:=1 to n do

  b[i]:=maxint;

 b[n]:=0;

 for i:= n-1 downto 1 do

  for j:=n downto i+1 do

   if (a[i,j]>0) and (b[j]<>maxint) and (b[j]+a[i,j]

    then begin b[i]:=b[j]+a[i,j];c[i]:=j end;

 writeln('minlong=',b[1]);

 x:=1;

  while x<>0 do

   begin

   write(x:5);

   x:=c[x];

  end;

end.

3.4习题

1.若城市路径示意图如下图所示:

图中，每条边上的数字是这段道路的长度。条件：从A地出发，只允许向右或向上走。试寻找一条从A地到B地的最短路径和长度。

2.求一个数列中的连续若干个数和的最大值.

3.资源分配问题:n个资源分配到m个项目上，i项目分配j个资源可获益a[i,j],求最大总效益。

4.  装箱问题

问题描述:有一个箱子容量为V（正整数，0＜＝V＜＝20000），同时有n个物品（0＜n＜＝30，每个物品有一个体积（正整数）。要求n个物品中，任取若干个装入箱内，使箱子的剩余空间为最小。

        样例

        输入：

24             一个整数，表示箱子容量

6   一个整数，表示有n个物品

8　 接下来n行，分别表示这n 个物品的各自体积

3

12

7

9

7

输出：

0　　一个整数，表示箱子剩余空间。

第四章 动态规划的递归函数法

4.1 原始递归法

先看完全背包问题

一个旅行者有一个最多能用m公斤的背包，现在有n种物品，每件的重量分别是W1，W2，...,Wn,

每件的价值分别为C1,C2,...,Cn.若的每种物品的件数足够多.

求旅行者能获得的最大总价值。

本问题的数学模型如下：

设 f(x)表示重量不超过x公斤的最大价值，

则 f(x）=max{f(x-i)+c[i]}  当x>=w[i] 1<=i<=n

可使用递归法解决问题程序如下:

program knapsack04;

 const maxm=200;maxn=30;

 type ar=array[0..maxn] of integer;

 var m,n,j,i,t:integer;

 c,w:ar;

function f(x:integer):integer;

var i,t,m:integer;

begin

 if x=0 then  f:=0 else

  begin

   t:=-1;

   for i:=1 to n do

    begin

     if x>=w[i] then m:=f(x-i)+c[i];

     if m>t then t:=m;

    end;

   f:=t;

   end;

end;

begin

  readln(m,n);

  for i:= 1 to n do

   readln(w[i],c[i]);

    writeln(f(m));

  end.

说明:当m不大时,编程很简单,但当m较大时,容易超时.

4.2 改进的递归法

改进的的递归法的思想还是以空间换时间,这只要将递归函数计算过程中的各个子函数的值保存起来,开辟一个

一维数组即可

程序如下:

program knapsack04;

 const maxm=2000;maxn=30;

 type ar=array[0..maxn] of integer;

 var m,n,j,i,t:integer;

 c,w:ar;

p:array[0..maxm] of integer;

function f(x:integer):integer;

var i,t,m:integer;

begin

if p[x]<>-1 then   f:=p[x] 

 else 

  begin

  if x=0 then  p[x]:=0 else

    begin

     t:=-1;

     for i:=1 to n do

      begin

       if x>=w[i] then m:=f(i-w[i])+c[i];

       if m>t then t:=m;

      end;

     p[x]:=t;

   end;

  f:=p[x];

 end;

end;

begin

  readln(m,n);

  for i:= 1 to n do

   readln(w[i],c[i]);

 fillchar(p,sizeof(p),-1);    

writeln(f(m));

  end.

4.3习题

用改进的递归法解资源分配问题:

n个资源分配到m个项目上，i项目分配j个资源可获益a[i,j],求最大总效益。

第五章 动态规划分类1

5.1 例1

乘积最大问题

问题描述：

　　今年是国际数学联盟确定的"2000--世界数学年"，又恰逢我国著名数学家华罗庚先生诞辰90周年。在华罗庚先生的家乡江苏金坛，组织了一场别开生面的数学智力竞赛的活动，你的一个好朋友XZ也有幸得以参加。活动中，主持人给所有参加活动的选手除了这样一道题目：

　　设有一个长度为N的数字串，要求选手使用K个乘号将它分成K+1个部分，找出一种分法，使得这K+1部分的乘积能够为最大。

　　同时，为了帮助选手能够正确理解题意，主持人还举了如下的一个例子：

　　有一个数字川：312，当N=3,K=1时会有一下两种分法：

1） 3*12=36

2） 31*2=62

　　这时，符合题目要求的结果是；31*2=62

　　现在，请你帮助你的好朋友XZ设计一个程序，求得正确的答案。

输入：

　　程序的输入共有两行：

　　第一行共有2个自然数N，K（6≤N≤50，1≤K≤20）

　　第二行是一个长度为N的数字串。

输出：

　　结果显示在屏幕上，相对于输入，应输出所求得的最大乘积（一个自然数）。

样例：

输入

4 2

1231

输出

62

程序如下：

program tg20002;

const maxn=50;maxk=20 ;

type num=record

       len:byte;

       s:array[1..maxn] of byte;

       end;

type str=string[maxn];

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

    st,temps:str;

    m,tempm:num;

    f:array[1..maxn] of num;

    s1:array[1..maxn] of str;

procedure strtonum(str1:str;var num1:num);

var i:integer;

begin

 num1.len:=length(str1);

 for i:=1 to num1.len do

  num1.s[i]:=ord(str1[num1.len-i+1])-ord('0');

end;

procedure mult(x,y:num;var z: num );

var i,j,len:integer;

begin

fillchar(z,sizeof(z),0);

 for i:= 1 to x.len do

  for j:=1 to y.len do

   begin

    inc(z.s[i+j-1], x.s[i]*y.s[j]);

    inc(z.s[i+j],z.s[i+j-1] div 10);

    z.s[i+j-1]:=z.s[i+j-1] mod 10;

   end;

 len:=x.len+y.len+1;

 while (len>1) and (z.s[len]=0) do len:=len-1;

 z.len:=len;

end;

procedure bigger(x,y:num;var z:num);

var i:integer;

begin

 if x.len>y.len then begin z.len:=x.len;z.s:=x.s end else

 if x.len

  begin

   z.len:=x.len;

   i:=z.len;

   while (i>1) and (x.s[i]=y.s[i]) do i:=i-1;

   if x.s[i]>=y.s[i] then z.s:=x.s else z.s:=y.s;

 end;

end;

begin

 readln(n,k);

 readln(st);

 fillchar(f,sizeof(f),0);

 for i:=1 to n do

  begin

   s1[i]:=copy(st,1,i);

   strtonum(s1[i],f[i]);

  end;

 for i:=2 to k+1 do

  for j:=n downto i do

   begin

    fillchar(m,sizeof(m),0);

     for l:=i-1 to j-1 do

      begin

       temps:=copy(s1[j],l+1,j-l);

       strtonum(temps,tempm);

       mult(f[l],tempm, tempm);

       bigger(m,tempm,m);

      end;

    f[j]:=m;

  end;

l:=f[n].len;

while (l>1) and (f[n].s[l]=0) do l:=l-1;

 for i:=l downto 1 do write(f[n].s[i]);

writeln;

end.

5.2 例2

统计单词个数 

[问题描述]

　　给出一个长度不超过200的由小写英文字母组成的字符串（约定：该字串以每行20个字母的方式输入，且保证每行一定为20个）。要求将此字串分成k份（1≤40），且每份中包含的单词个数加起来总数最大（每份中包含的单词可以部分重叠。当选用一个单词之后，其第一个字母不能再用。例如字符串this中可以包含this和is，选用this之后就不能包含th）。

　　单词在给出的一个不超过6个单词的字典中。

　　要求输出最大的个数。

[输入格式]

　　全部输入数据存放在文本文件input3.dat中，其格式如下：

　　第一行为一个正整数(0≤5)表示有n组测试数据

　　每组的第一行有二个正整数：（p,k)

　　　　p表示字串的行数；

　　　　k表示分为k个部分。

　　接下来的p行，每行均有20个字符。

　　再接下来有一个正整数s，表示字典中单词个数。（1≤s≤6）

　　接下来的s行，每行均有一个单词。

[输出格式]

　　结果输出至屏幕，每行一个整数，分别对应每组测试数据的相应结果。

[样例]

输入：1

　　　1 3

　　　thisisabookyouareaoh

　　　4

　　　is

　　　a

　　　ok

　　　sab

输出：　　　　　//说明：（不必输出）

　　　7 　　　　// this/isabookyoua/reaoh

　　　　　　　　　　　　 sab

program tg20013;

const maxl=200;

type chararr=string[maxl];

var n,p,k,s,l,i,max: integer;

word:array[1..6] of chararr;

s1:chararr;

str:array[1..10] of string[20];

fi:text;

f:array[1..maxl] of integer;

len:array[1..maxl] of integer;

g:array[1..maxl,1..maxl] of byte;

function plus(str:chararr):integer;

 var l1,r,i,j,x:integer;

   b:array[1..200] of boolean;

 begin

 x:=0;

 l1:=length(str);

 fillchar(b,sizeof(b),true);

 for j:= 1 to s do

  begin

   r:=length(word[j]);

   for i:= 1 to l1 do

    if (word[j]=copy(str,i,r)) and b[i] then begin b[i]:=false;x:=x+1 end

  end;

 plus:=x;

 end;

procedure calclen;

var i,j:integer;

begin

 for i:=1 to l do len[i]:=200;

 for i:=1 to l do

  for j:=1 to s do

   if copy(s1,i,length(word[j]))=word[j] then if

   len[i]>length(word[j]) then len[i]:=length(word[j]);

end;

procedure calc_g;

var i,j:integer;

begin

 fillchar(g,sizeof(g),0);

 for i:=l downto 1 do

 begin

  if len[i]=1 then g[i,i]:=1 ;

  for j:=l-1 downto 1 do

   if len[j]<=i-j+1 then g[j,i]:=g[j+1,i]+1 else g[j,i]:=g[j+1,i];

 end;

end;

procedure calc;

var  i,j,m,maxt,t:integer;stri:string;

begin

 for i:=1 to l do

  f[i]:=plus(copy(s1,1,i));

 for i:=2 to k do

   begin

    for j:=l downto 1 do

      begin

       maxt:=0;

       for m:=i-1 to j-1 do

         begin

         t:=f[m]+g[m+1,j];

         if t>maxt then maxt:=t;

         end;

        f[j]:=maxt;

      end;

 end;

end;

begin

 assign(fi,'input3.dat');

 reset(fi);

 readln(fi,n);

 repeat

  dec(n);

  readln(fi,p,k);

  s1:='';

  for i:=1 to p do

   begin

    readln(fi,str[i]);

    s1:=s1+str[i];

   end;

  l:=length(s1);

  readln(fi,s);

  for i:=1 to s do

   readln(fi,word[i]);

  calclen;

  calc_g;

  calc;

  writeln(f[l]);

  until n=0;

end.

5.3 例3

2002年第四题：

求：平面上的n个点用k个矩形覆盖的最小面积？

程序如下：

program tg20024;

const maxn=50;

type pointset=array[1..maxn,1..2] of longint;

var

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

 a:pointset;

 f:array[1..maxn] of longint;

maxs,min,t:longint;

procedure init;

 var i:integer;

     filename:string[20];

     f:text;

begin

 readln(filename);

 assign(f,filename);

 reset(f);

 readln(n,k);

 for i:= 1 to n do

  readln(a[i,1],a[i,2]);

 close(f);

end;

procedure sort(var x:pointset);

var i,j,m:integer;

   t1,t2,t3:integer;

begin

 for i:=1 to n-1 do

  begin

   t1:=x[i,1];t2:=x[i,2];t3:=t2;m:=i;

   for j:= i+1 to n do

    if t3>x[j,2] then begin m:=j; t3:=x[j,2];end;

   if m<>i then

   begin x[i,1]:=x[m,1];x[i,2]:=x[m,2];x[m,1]:=t1;x[m,2]:=t2 end;

  end;

end;

function maxy(x0,xn:integer):integer;

var i,max:integer;

begin

 max:=0;

 for i:=x0 to xn do

   if max

maxy:=max;

end;

function miny(x0,xn:integer):integer;

var i,min:integer;

begin

 min:=32767;

 for i:=x0 to xn do

   if min>a[i,1] then min:=a[i,1];

miny:=min;

end;

begin

 init;

 sort(a);

 fillchar(f,sizeof(f),0);

 maxs:=(a[n,2]-a[1,2])*(maxy(1,n)-miny(1,n));

 for i:= 1 to n do

 f[i]:=(a[i,2]-a[1,2])*(maxy(1,i)-miny(1,i));

 for i:=2 to k do

   for j:= n downto 1 do

     begin

        min:=maxs;

        for l:=i-1 to j-1 do

         begin

           t:=f[l]+(a[j,2]-a[l+1,2])*(maxy(l+1,j)-miny(l+1,j));

           if (ta[l+1,2]) then min:=t;

         end;

       f[j]:=min;

      end;

writeln(f[n]);

end.

练习：

Barn Repair

It was a dark and stormy night that ripped the roof and gates off the stalls that hold Farmer John's cows. Happily, many of the cows were on vacation, so the barn was not completely full.

The cows spend the night in stalls that are arranged adjacent to each other in a long line. Some stalls have cows in them; some do not. All stalls are the same width.

Farmer John must quickly erect new boards in front of the stalls, since the doors were lost. His new lumber supplier will supply him boards of any length he wishes, but the supplier can only deliver a small number of total boards. Farmer John wishes to minimize the total length of the boards he must purchase.

Given M (1 <= M <= 50), the maximum number of boards that can be purchased; S (1 <= S <= 200), the total number of stalls; C (1 <= C <= S) the number of cows in the stalls, and the C occupied stall numbers (1 <= stall_number <= S), calculate the minimum number of stalls that must be blocked in order to block all the stalls that have cows in them.

Print your answer as the total number of stalls blocked.

PROGRAM NAME: barn1

INPUT FORMAT

SAMPLE INPUT (file barn1.in)

4 50 18

3

4

6

8

14

15

16

17

21

25

26

27

30

31

40

41

42

43

OUTPUT FORMAT

A single line with one integer that represents the total number of stalls blocked.

SAMPLE OUTPUT (file barn1.out)

25

[One minimum arrangement is one board covering stalls 3-8, one covering 14-21, one covering 25-31, and one covering 40-43.]

程序如下：

program barn1;

const maxm=50;maxs=200;

var m,s,c,i,n:integer;

   a:array[1..maxs,1..maxs] of byte;

   b:array[1..maxs] of boolean;

   f:array[1..maxs] of integer;

f1,f2:text;

function minl(x,y:integer):integer;

var i,j:integer;

begin

i:=x;j:=y;

while not(b[i]) and (i<=y) do inc(i);

while not(b[j]) and (j>=x) do dec(j);

if i<=j then minl:=j-i+1 else minl:=0;

end;

procedure calac_a;

var i,j:integer;

begin

for i:=1 to s do

 for j:=1 to s do

  a[i,j]:=minl(i,j);

end;

procedure main;

var i,j,k,min:integer;

begin

 fillchar(f,sizeof(f),0);

 calac_a;

 for i:=1 to s do

 f[i]:=a[1,i];

 for i:= 2 to m do

  for j:=s downto i  do

    begin

     min:=200;

     for k:=i-1 to j-1 do

       if f[k]+a[k+1,j]

     f[j]:=min;

   end;

end;

begin

 assign(f1,'barn1.in');

 reset(f1);

 readln(f1,m,s,c);

 fillchar(b,sizeof(b),false);

 for i:=1 to c do

 begin

  readln(f1,n);

  b[n]:=true;

 end;

 close(f1);

 assign(f2,'barn1.out');

 main;

 rewrite(f2);

 writeln(f2,f[s]);

 close(f2);

end.

信息竞赛复习资料5--动态规划(NOIP)