当前位置:首页 >> 学科竞赛 >> Pascal动态规划-复习2

Pascal动态规划-复习2


动态规划---复习篇
Dynamic Programming

多阶段决策过程的最优化问题
● 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)丰富了计算结果 ● 从此例的求解结果中,我们不仅得到由 A点出发到终点E的最短路线及最短距 离,而且还得到了从所有各中间点到终 点的最短路线及最短距离,这对许多实 际问题来讲是很有用的。

● 动态规划的最优化概念是在一定条件下,找到一 种途径,在对各阶段的效益经过按问题具体性质 所确定的运算以后,使得全过程的总效益达到最 优。 ● 应用动态规划要注意阶段的划分是关键,必须依 据题意分析,寻求合理的划分阶段(子问题)方法。 ● 而每个子问题是一个比原问题简单得多的优化问 题。而且每个子问题的求解中,均利用它的一个 后部子问题的最优化结果,直到最后一个子问题 所得最优解,它就是原问题的最优解。

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

● 准确地说,动态规划不是万能的,它只适于解决一定条件的最优策略 问题。 ● (1)状态必须满足最优化原理; (2)状态必须满足无后效性 ● 1、动态规划的最优化原理是指无论过去的状态和决策如何,对前面 的决策所形成的当前状态而言,余下的诸决策必须构成最优策略。 ● 可以通俗地理解为子问题的局部最优将导致整个问题的全局最优在上 例最短路径问题中,A到E的最优路径上的任一点到终点E的路径也必 然是该点到终点E的一条最优路径,满足最优化原理。 ● 动态规划的无后效性原则指某阶段的状态一旦确定,则此后过程的演 变不再受此前各状态及决策的影响。也就是说,“未来与过去无关”, 当前的状态是此前历史的一个完整总结,此前的历史只能通过当前的 状态去影响过程未来的演变。具体地说,如果一个问题被划分各个阶 段之后,阶段 I 中的状态只能由阶段 I+1 中的状态通过状态转移方程 得来,与其他状态没有关系,特别是与未发生的状态没有关系,这就 是无后效性。

数塔
● 如下图所示的数塔,从顶部出发,在每一结点可以选择向左下走或是 向右下走,一直走到底层,要求找出一条路径,使路径上的数的和最 大。数塔层数用n表示,1<=n<=100。 ● 【分析】对于这一问题,很容易想到用枚举的方法(深度搜索法)去 解决,即列举出所有路径并记录每一条路径所经过的数字总和。然后 寻找最大的数字总和,这一想法很直观,很容易编程实现。 ● 但是当行数很大时,当三角形的行数等于100时,其枚举量之大是可 想而知的,用枚举法肯定超时,甚至根本不能得到计算结果,必须用 动态规划法来解。

怎样用动态规划法解题
● 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 n,i,j:integer; a:array[1..maxn,1..maxn] of integer; f:array[1..maxn,1..maxn] of integer; begin readln(n); for i:=1 to n do for j:=1 to i do read(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 n,i,j:integer; a:array[1..maxn,1..maxn] of integer; f:array[1..maxn,1..maxn] of integer; maxsum:integer; begin readln(n); for i:=1 to n do for j:=1 to i do read(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)三要素法 仔细分析问题尝试着确定动态规划的三要素,不同问题的却定方向不同: 先确定阶段的问题:数塔问题,和走路问题(详见解题报告) 先确定状态的问题:大多数都是先确定状态的。 先确定决策的问题:背包问题。(详见解题报告) 一般都是先从比较明显的地方入手,至于怎么知道哪个明显就是经验问题了,多做题 就会发现。 (3)寻找规律法: 这个方法很简单,耐心推几组数据后,看他们的规律,总结规律间的共性,有点贪心 的意思。 (4)边界条件法 找到问题的边界条件,然后考虑边界条件与它的领接状态之间的关系。这个方法也很 起效。 (5)放宽约束和增加约束 具体内容就是给问题增加一些条件或删除一些条件使问题变的清晰。

● ●
● ●

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

● 动态规划所处理的问题是一个多阶段决策问题,一般由初始状态开始,通 过对中间阶段决策的选择,达到结束状态。这些决策形成了一个决策序列, 同时确定了完成整个过程的一条活动路线(通常是求最优的活动路线)。动 态规划的设计都有着一定的模式,一般要经历以下几个步骤。 ● (1)划分阶段:按照问题的时间或空间特征,把问题分为若干个阶段。在划 分阶段时,注意划分后的阶段一定要是有序的或者是可排序的,否则问题 就无法求解。 ● (2)确定状态和状态变量:将问题发展到各个阶段时所处于的各种客观情况 用不同的状态表示出来。当然,状态的选择要满足无后效性。 ● (3)确定决策并写出状态转移方程:因为决策和状态转移有着天然的联系, 状态转移就是根据上一阶段的状态和决策来导出本阶段的状态。所以如果 确定了决策,状态转移方程也就可写出。但事实上常常是反过来做,根据 相邻两段各状态之间的关系来确定决策。 ● (4)寻找边界条件:给出的状态转移方程是一个递推式,需要一个递推的终 止条件或边界条件。 ● (5)程序设计实现:动态规划的主要难点在于理论上的设计,一旦设计完成, 实现部分就会非常简单。

动态规划解题框架
● 根据上述动态规划设计的步骤,可得到大体解题框架如下: ● 1.初始化(边界条件) ● 2.for i:=2 to n (顺推法) 或 for i:=n-1 downto 1(逆推法) ● 对i阶段的每一个决策点求局部最优 ● 3.确定和输出结束状态的值.
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;

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];

最大不下降序列问题
● (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<i2<i3< … < ie 且有a(i1)<a(i2)< … <a(ie) 则称为长度为e的不下降序列。 ● 如上例中3,18,23,24就是一个长度为4的不下 降序列,同时也有3,7,10,12,16,24长度为 6的不下降序列。 ● 程序要求,当原数列给出之后,求出最长的不下 降序列。

状态是一维的:下降/非降子序列问题
● 如果前i-1个数中用到ak (ak>ai或ak<=ai)构成了一个的最长的序列加 上第I个数ai就是前i个数中用到i的最长的序列了。那么求用到ak构成 的最长的序列有要求前k-1个数中…… ● 从上面的分析可以看出这样划分问题满足最优子结构,那满足无后效 性么?显然对于第i个数时只考虑前i-1个数,显然满足无后效性,可以 用动态规划解。 ● 分析到这里动态规划的三要素就不难得出了:如果按照序列编号划分 阶段,设计一个状态opt[i] 表示前i个数中用到第i个数所构成的最优解。 ● 那么决策就是在前i-1个状态中找到最大的opt[j]使得aj>ai(或aj<=ai), opt[j]+1就是opt[i]的值;用方程表示为:{我习惯了这种写法,但不是 状态转移方程的标准写法 } ● opt[i]=max(opt[j])+1 (0<=j<i 且aj<=ai) {最长非降子序列} ● opt[i]=max(opt[j])+1 (0<=j<i 且aj>ai) {最长下降子序列}

状态是一维的:下降/非降子序列问题
● ● ● ● ● ● ● ● ● ● 实现求解的部分代码: opt[0]:=maxsize;{maxsize 为maxlongint或-maxlongint} for i:=1 to n do for j:=0 to i-1 do if ( a[j]>a[i]) and (opt[j]+1>opt[i]) then opt[i]:=opt[j]+1; ans:=-maxlongint; for i:=1 to n do if opt[i]>ans then ans:=opt[i]; {ans 为最终解} 复杂度:从上面的实现不难看出时间复杂度为O(N2), 空间复杂度O(N);

状态是一维的:下降/非降子序列问题
● 分析到这里动态规划的三要素就不难得出了:如果按照序列编号划分阶段, 设计一个状态opt[i] 表示前i个数中用到第i个数所构成的最优解。那么决策就 是在前i-1个状态中找到最大的opt[j]使得aj>ai(或aj<=ai),opt[j]+1就是opt[i]的 值;用方程表示为:{我习惯了这种写法,但不是状态转移方程的标准写法 } ● opt[i]=max(opt[j])+1 (0<=j<i 且aj<=ai) {最长非降子序列} ● opt[i]=max(opt[j])+1 (0<=j<i 且aj>ai) {最长下降子序列} ● 实现求解的部分代码: ● opt[0]:=maxsize;{maxsize 为maxlongint或-maxlongint} ● for i:=1 to n do ● for j:=0 to i-1 do ● if ( a[j]>a[i]) and (opt[j]+1>opt[i]) then ● opt[i]:=opt[j]+1; ● ans:=-maxlongint; ● for i:=1 to n do ● if opt[i]>ans then ans:=opt[i]; {ans 为最终解} ● 复杂度:从上面的实现不难看出时间复杂度为O(N2),空间复杂度O(N);

【分析】
设F(i)为前I个数中的最大不下降序列长度。由题意不难得知,要求F(i), 需要求得F(1)—F(i-1),然后选择一个最大的F(j) ( j<i, bi>bj ),那么前I 个数中最大不下降序列便是前j个数中最大不下降序列后添加bi而得。 可见此任务满足最优子结构,可以用动态规划解决。 通过上面的分析可得状态转移方程如下: F(i)=max{F(j)+1} (j<i, bj<bi) 边界为F(1)=1 【部分代码】 f[1]:=1;len:=1; {求解最大不下降序列长度} for i:=2 to n do begin f[i]:=1; for j:=1 to i-1 do if (b[i]>b[j])and(f[i]<f[j]+1) then f[i]:=f[j]+1; if f[i]>len then len:=f[i] {记录最大值}

算法分析
● 根据动态规划的原理,由后往前进行搜索。 ● 1·对a(n)来说,由于它是最后一个数,所以当从a(n) 开始查找时,只存在长度为1的不下降序列; ● 2·若从a(n-1)开始查找,则存在下面的两种可能性: ①若a(n-1)<a(n)则存在长度为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后继接点的编号

● (逆推法) ● program li1; const maxn=100; var a,b,c:array[1..maxn] of integer; n,i,j,max,p:integer; begin readln(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]<a[j]) and (b[j]>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.

Sample Problem1
合唱队形(NOIp2004)
【问题描述】 N位同学站成一排,音乐老师要请其中的(N-K)位同学出列,使得剩下的K 位同学排成合唱队形。 合唱队形是指这样的一种队形:设K位同学从左到右依次编号为1,2…,K, 他 们 的 身 高 分 别 为 T1 , T2 , … , TK , 则他们的身高满足 T1<...<Ti>Ti+1>…>TK(1<=i<=K) 。 你的任务是,已知所有N位同学的身高,计算最少需要几位同学出列,可 以使得剩下的同学排成合唱队形。 【输入文件】 输入文件第一行是一个整数N(2<=N<=100),表示同学的总数。第一行有n 个整数,用空格分隔,第i个整数Ti(130<=Ti<=230)是第i位同学的身高。 【输出文件】 输出文件包括一行,这一行只包含一个整数,就是最少需要几位同学出列。

Sample Problem2
拦截导弹(NOIp1999)
某国为了防御敌国的导弹袭击,发展出一种导弹拦截系统。但是这种导弹拦 截系统有一个缺陷:虽然它的第一发炮弹能够到达任意的高度,但是以后每一发 炮弹都不能高于前一发的高度。某天,雷达捕捉到敌国的导弹来袭。由于该系统 还在试用阶段,所以只有一套系统,因此有可能不能拦截所有的导弹。 输入导弹依次飞来的高度(雷达给出的高度数据是不大于30000的正整数), 计算这套系统最多能拦截多少导弹,如果要拦截所有导弹最少要配备多少套这种 导弹拦截系统。 样例: INPUT 389 207 155 300 299 170 158 65 统数)

OUTPUT 6(最多能拦截的导弹数) 2(要拦截所有导弹最少要配备的系

Sample Problem3
【问题描述】 “逢低吸纳”是炒股的一条成功秘诀。如果你想成为一个成功的投资者,就要遵守这条秘诀:"逢低吸纳,越 低越买" 这句话的意思是:每次你购买股票时的股价一定要比你上次购买时的股价低.按照这个规则购买股票的次 数越多越好,看看你最多能按这个规则买几次。 给定连续的N天中每天的股价。你可以在任何一天购买一次股票,但是购买时的股价一定要比你上次购买 时的股价低。写一个程序,求出最多能买几次股票。 以下面这个表为例, 某几天的股价是: 天数 1 2 3 4 5 6 7 8 9 10 11 12 股价 68 69 54 64 68 64 70 67 78 62 98 87 这个例子中, 聪明的投资者(按上面的定义),如果每次买股票时的股价都比上一次买时低,那么他最多能 买4次股票。一种买法如下(可能有其他的买法): 天数 2 5 6 10 股价 69 68 64 62 【输入文件】buylow.in 第1行: N (1 <= N <= 5000), 表示能买股票的天数。 第2行以下: N个正整数 (可能分多行) ,第i个正整数表示第i天的股价. 这些正整数大小不会超过 longint(pascal)/long(c++). 【输出文件】buylow.out 只有一行,输出两个整数: 能够买进股票的天数长度达到这个值的股票购买方案数量 在计算解的数量的时候,如果两个解所组成的字符串相同,那么这样的两个解被认为是相同的(只能算做 一个解)。因此,两个不同的购买方案可能产生同一个字符串,这样只能计算一次。

【问题分析】

Sample Problem4 【问题描述】
PALMIA国家被一条河流分成南北两岸,南北两岸上各有N个村庄。北岸的每一个村庄有一个唯一的朋友 在南岸,且他们的朋友村庄彼此不同。 每一对朋友村庄想要一条船来连接他们,他们向政府提出申请以获得批准。由于河面上常常有雾,政府决 定禁止船只航线相交(如果相交,则很可能导致碰船)。 你的任务是编写一个程序,帮助政府官员决定批准哪些船只航线,使得不相交的航线数目最大。 【输入文件】ships.in 输入文件由几组数据组成。每组数据的第一行有2个整数X,Y,中间有一个空格隔开,X代表PALMIA河 的长度(10<=X<=6000),Y代表河的宽度(10<=Y<=100)。第二行包含整数N,表示分别坐落在南北 两岸上的村庄的数目(1<=N<=5000)。在接下来的N行中,每一行有两个非负整数C,D,由一个空格隔 开,分别表示这一对朋友村庄沿河岸与PALMIA河最西边界的距离(C代表北岸的村庄,D代表南岸的村 庄),不存在同岸又同位置的村庄。最后一组数据的下面仅有一行,是两个0,也被一空格隔开。 【输出文件】ships.out 对输入文件的每一组数据,输出文件应在连续的行中表示出最大可能满足上述条件的航线的数目。 【输入样例】 30 4 7 22 4 26 10 3 15 12 98 17 17 42 00 【输出样例】 4


更多相关文档:

动态规划36讲

18页 2财富值 动态规划专项练习题解 30页 2财富值如要投诉违规内容,请到百度...动态规划 极品 pascal动态规划 极品 pascal隐藏>> 一,动态规划三要素:阶段,状态...

动态规划PASCAL

动态规划PASCAL_广告/传媒_人文社科_专业资料。PASCAL的部分教程 以后还会添加的哦...练习:用一维数组和逆推法解本题. . 2.3 用动态规划法解题的一般模式 动态...

Pascal动态规划模型一

41页 5财富值 pascal中级教程第八章动态... 16页 免费 Pascal动态规划-复习 42页 2财富值 Pascal动态规划-复习2 29页 2财富值喜欢此文档的还喜欢 ...

动态规划入门2

pascal语言pascal语言隐藏>> 动态规划入门 §1.引例例 1:题一.如下图有一个...下列两个条件之一: 1、它是该次测试中第一个被防卫导弹截击的导弹; 2、它...

动态规划讲稿2

线性规划讲稿2 48页 免费喜欢此文档的还喜欢 生产与存储的动态规划模型 6页 1财富值 多种画面动画效果动态PPT模... 7页 免费 Pascal动态规划 22页 免费 动态...

动态规划专题

关键词:pascal语言动态规划专题 1/2 相关文档推荐 动态规划专题 123页 免费 专题...及相关的优化方法 把讲稿的相关内容再复习一遍, 把讲稿的相关内容再复习一遍, ...

动态规划(2011网上函授第三讲)

动态规划_周谷越 51页 免费 pascal竞赛辅导教案 45页 5财富值如要投诉违规内容...(0<n≤5)表示有 n 组测试数据,每组的第一行有二个正 整数:(p,k),其中 ...

pascal教程8--动态规划

pascal教程8--动态规划_计算机软件及应用_IT/计算机_专业资料。pascal教程第...对于图 8-1 中的例子,只要将最后一个多米诺骨牌旋转 180°,可使上下 2 行...

【Pascal-C++】资源类动态规划练习题

Pascal-C++】资源类动态规划练习题_计算机软件及应用_IT/计算机_专业资料。【...【输入样例】 1000 5 800 2 400 5 300 5 400 3 200 2 【输出样例】 ...

算法-动态规划

关键词:pascal动态规划 1/2 相关文档推荐 动态规划算法 10页 免费 算法-动态规划...594 毫秒 测试结果 1: 通过本测试点|有效耗时 172ms 测试结果 2: 通过本...
更多相关标签:
网站地图

文档资料共享网 nexoncn.com copyright ©right 2010-2020。
文档资料共享网内容来自网络,如有侵犯请联系客服。email:zhit325@126.com