中华中学动态规划讲义.pptVIP

中华中学动态规划讲义 周默 介绍 动态规划是NOIP中非常重要的一类题型 在动态规划中 算法是最难想到的 当你想到了算法 实现也就迎刃而解 今天 我们将强调算法的研究 不作上机实践 递推 递推是动态规划的根本 我们首先花一点时间进行递推训练 递推关系是一种简洁高效的常见数学模型 比如我们熟悉的Fibonacci数列问题 在这种类型的问题中 每个数据项都和它前面的若干个数据项 或后面的若干个数据项 有一定的关联 这种关联一般是通过一个 递推关系式 来表示的 求解问题时我们从初始的一个或若干个数据项出发 通过递推关系逐步推进 从而得到最终结果 这种求解问题的方法叫 递推法 其中 初始的若干数据项称为 边界 解决递推问题有三个重点 一 如何建立正确的递推关系二 递推关系有何性质三 递推关系式如何求解 递推按照我们推导问题的方向 常分为顺推法和倒推法 例1 有一只经过训练的蜜蜂只能爬向右侧相邻的蜂房 不能反向爬行 试求出蜜蜂从蜂房a爬到蜂房b的可能路线数 问题分析 这是一道很典型的Fibonacci数列类题目 其中的递推关系很明显 由于 蜜蜂只能爬向右侧相邻的蜂房 不能反向爬行 的限制 决定了蜜蜂到b点的路径只能是从b 1点或b 2点到达的 故fn fn 1 fn 2 a 2 n b 边界条件fa 1 fa 1 1 例2 打印杨晖三角形的前10行 杨晖三角形的前5行如左下图所示 问题分析 我们观察左上图不太容易找到规律 但如果将左上图转化为右上图就不难发现杨辉三角形其实就是一个二维表 数组 的下三角部分 假设用二维数组yh存储 每行首尾元素都为1 且其中任意一个非首尾元素yh i j 的值其实就是yh i 1 j 1 与yh i 1 j 的和 另外每一行的元素个数刚好等于行数 有了这些规律 给数组元素赋值就不难了 而要打印杨晖三角形 只需控制一下每行输出的起始位置即可 例3 猴子第1天摘下若干个桃子 当即吃了一半又一个 第2天又把剩下的桃吃了一半又一个 以后每天都吃前一天剩下的桃子的一半又一个 到第10天猴子想吃时 只剩下一个桃子 问猴子第1天一共摘了多少桃子 问题分析 已知条件第10天剩下1个桃子 隐含条件每一次前一天的桃子个数等于后一天桃子的个数加1的2倍 我们采取逆向思维的方法 从后往前推 可用倒推法求解 VarS I LongInt BeginS 1 第10天只有一个桃子 ForI 9DownTo1DoS S 1 2 第10天依次求前一天的桃Writeln S 子数 End 程序填空 设有一个n级的楼梯 1 n 12 编号从下到上依次为1至n 其中有若干级为坏的 有一个人上楼梯时一步可走1级 或2级 或3级 坏级只能跨过不能踏上 但级数照算 问 这个人从楼下走到第n级 共有多少种不同的走法 例如 当n l时 无坏级情况下 仅有1种走法n 2时 无坏级情况下 有 1级 l级或2级共2种走法n 3时 第二级为坏级情况下 有 1级 2级 直接3级 共2种走法 程序说明 用递推方法求解 用集合记录坏级 varx i n fl f2 f3 f4 longint s setof0 30 beginreadln n s readln x x 坏级 以0结束 while xO dobegins readln x end If 1ins thenf1 0elsefl 1 If 2ins thenf2 0elsef2 If 3ins thenf3 0elsef3 1 f1 f2 ifn 1thenf4 f1elseifn 2thenf4 f2elseifn 3thenf4 f3elsebeginfori 4tondobeginif iins thenf4 0elsef4 fl f2 f2 f3 f3 f4 end end writeln f4 readln end 例4 棋盘上A点有一个过河卒 需要走到目标B点 卒行走的规则 可以向下 或者向右 同时在棋盘上C点有一个对方的马 该马所在的点和所有跳跃一步可达的点称为对方马的控制点 因此称之为 马拦过河卒 棋盘用坐标表示 A点 0 0 B点 n m n m为不超过15的整数 同样马的位置坐标是需要给出的 现在要求你计算出卒从A点能够到达B点的路径的条数 假设马的位置是固定不动的 并不是卒走一步马走一步 样例 knight inknight out66336 分析 本题可用搜索算法 但N M 15就会超时 再分析题意会发现 要到达棋盘上的一个点 只能从左边过来或是从上面过来 根据加法原理 到达某一点的路径数目 就等于到达其相邻的上点和左点的路径数目之和 因此我们可以使用逐列 或逐行 递推的方法来求出从起点到终点的路径数目 障碍点 马的控制点 也完全适用 只要将到达该点的路径数目设置为0即可 假设用f i j 表示到达点 i j 的路径数目 用g i j 表示点 i j 是否是对方马的控制点 g i j 0表示不是对方马的控制点 g i j 1表示是对方马的控制点 则 我们可以得到如下的递推关系式 递推边界为f 0 0 1 考虑到最大情况下 n 20 m 20 路径条数可能会超出长整数范围所以要使用Comp类型或高精度运算 f i j 0 g x y 1 f i 0 f i 1 0 i 0 g x y 0 f 0 j f 0 j 1 j 0 g x y 0 f i j f i 1 j f I j 1 i 0 j 0 g x y 0 例5 NOIP普及组第四题 给定A B C三根足够长的细柱 在A柱上放有2n个中间有空的圆盘 共有n个不同的尺寸 每个尺寸都有两个相同的圆盘 注意这两个圆盘是不加区分的 下图为n 3的情形 现要将这些国盘移到C柱上 在移动过程中可放在B柱上暂存 要求 1 每次只能移动一个圆盘 2 A B C三根细柱上的圆盘都要保持上小下大的顺序 任务 设An为2n个圆盘完成上述任务所需的最少移动次数 对于输入的n 输出An 输入 输入文件hanoi in为一个正整数n 表示在A柱上放有2n个圆盘 输出 输出文件hanoi out仅一行 包含一个正整数 为完成上述任务所需的最少移动次数An 输入输出样例1 hanoi inhanoi out12 问题分析 如果每个尺寸只有一个圆盘 共n个圆盘 也就是常见的汉诺塔问题 则设hn为n个盘子从a柱移到c柱所需移动的盘次 显然 当n 1时 只需把a柱上的盘子直接移动到c柱就可以了 故h1 1 当n 2时 先将a柱上面的小盘子移动到b柱上去 然后将大盘子从a柱移到c柱 最后 将b柱上的小盘子移到c柱上 共记3个盘次 故h2 3 以此类推 当a柱上有n n 2 个盘子时 总是先借助c柱把上面的n 1个盘子移动到b柱上 然后把a柱最下面的盘子移动到c柱上 再借助a柱把b柱上的n 1个盘子移动到c柱上 总共移动hn 1 1 hn 1个盘次 hn 2hn 1 1边界条件 hn 1 1 该题若仔细观察 很容易发现是hanoi塔的变形 只不过多了几个盘子 操作过程中 可以将两个相同尺寸的盘子看成一个整体 这样就成了典型的hanoi塔问题 再运用公式 f n 2n 1来做 最后只要乘2就行了 由于数据较大 须用到高精度运算 题型大类 简单线性dp背包最长XX子序列最长公共子序列LCS区间dp树dp坐标dp 1 数塔 738810277455265如图 有一数字三角形 数字三角形中的数字为不超过100的正整数 数字三角形中的数字为不超过100的正整数 现规定从最顶层走到最底层 每一步可沿左斜线向下或右斜线向下走 假设三角形行数 100 编程求解从最顶层走到最底层的一条路径 使得沿着该路径所经过的数字的总和最大 输出最大值 此数塔输出为30 是否可以用前两次课所用的深搜呢 显然前两次课的深搜写数塔这道题的时候程序简明易懂 但是当行数很大时 当三角形的行数等于100时 其枚举量之大是可想而知的 用枚举法肯定超时 甚至根本不能得到计算结果 必须用动态规划法来解 constmaxn 10 vara array 1 maxn 1 maxn ofinteger max longint n i j integer proceduretry x y dep integer sum longint beginif dep n thenbeginifsum maxthenmax sum exitend 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 beginreadln n fori 1tondoforj 1toidoread a i j max 0 try 1 1 1 a 1 1 writeln max end 那我们又该如何实现动态规划呢 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 nf i j max a i j f i 1 j a i j f i 1 j 1 1 j i f 1 1 即为所求 constmaxn 100 varn i j integer a array 1 maxn 1 maxn ofinteger f array 1 maxn 1 maxn ofinteger beginreadln n fori 1tondoforj 1toidoread a i j fori 1tondof n i a n i fori n 1downto1doforj 1toidoiff i 1 j f i 1 j 1 thenf i j a i j f i 1 j elsef 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 imax f n 1 f n 2 f n n 即为所求 constmaxn 100 varn i j integer a array 1 maxn 1 maxn ofinteger f array 1 maxn 1 maxn ofinteger maxsum integer beginreadln n fori 1tondoforj 1toidoread a i j fillchar f sizeof f 0 f 1 1 a 1 1 fori 2tondobeginf i 1 a i 1 f i 1 1 forj 2toidoiff i 1 j 1 f i 1 j thenf i j a i j f i 1 j 1 elsef i j a i j f i 1 j end maxsum 0 fori 1tondoiff n i maxsumthenmaxsum f n i writeln maxsum end 2 最长不下降子序列 设有由n个不相同的整数组成的数列 记为 a 1 a 2 a n 例如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的不下降序列 程序要求 当原数列给出之后 求出最长的不下降序列 constmaxn 100 vara b c array 1 maxn ofinteger n i j max p integer beginreadln n fori 1tondobeginread a i b n 1 c n 0 end fori n 1downto1dobeginmax 0 p 0 forj i 1tondoif a i max thenbeginmax b j p jend ifp0thenbeginb i b p 1 c i pendend max 0 p 0 fori 1tondoifb i maxthenbeginmax b i p iend writeln maxlong max whilep0dobeginwrite a p 5 p c p end end 谁能够说出刚刚做法的时间复杂度 n 2有没有速度更快的做法呢有 下面介绍nlogn的算法 varn i ans j k m longint a b array 1 10000 oflongint beginread n fori 1tondoread a i ans 0 fori 1tondobeginj 1 k ans whilejanstheninc ans b j a i end writeln ans end 同样的道理我们也可以做最长不上升子序列等等最长XX子序列 3 背包问题 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 若每种物品只有一件求旅行者能获得最大总价值 分析说明 显然这个题可用深度优先方法对每件物品进行枚举 选或不选用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 constmaxm 200 maxn 30 typear array 1 maxn ofinteger varm n j i integer c w ar f array 0 maxn 0 maxm ofinteger functionmax x y integer integer beginifx ythenmax xelsemax y end beginreadln m n fori 1tondoreadln w i c i fori 1tomdof 0 i 0 fori 1tondof i 0 0 fori 1tondoforj 1tomdobeginifj w i thenf i j max f i 1 j w i c i f i 1 j elsef i j f i 1 j end writeln f n m end 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思考 我们该如何把01背包改成完全背包呢 4 采药 辰辰是个天资聪颖的孩子 他的梦想是成为世界上最伟大的医师 为此 他想拜附近最有威望的医师为师 医师为了判断他的资质 给他出了一个难题 医师把他带到一个到处都是草药的山洞里对他说 孩子 这个山洞里有一些不同的草药 采每一株都需要一些时间 每一株也有它自身的价值 我会给你一段时间 在这段时间里 你可以采到一些草药 如果你是一个聪明的孩子 你应该可以让采到的草药的总价值最大 如果你是辰辰 你能完成这个任务吗 4 采药 输入文件 输入文件medic in的第一行有两个整数T 1 T 1000 和M 1 M 100 用一个空格隔开 T代表总共能够用来采药的时间 M代表山洞里的草药的数目 接下来的M行每行包括两个在1到100之间 包括1和100 的整数 分别表示采摘某株草药的时间和这株草药的价值 输出文件 输出文件medic out包括一行 这一行只包含一个整数 表示在规定的时间内 可以采到的草药的最大总价值 样例输入 7037110069112 样例输出 3 数据规模 对于30 的数据 M 10 对于全部的数据 M 100 5 开心的金明 金明今天很开心 家里购置的新房就要领钥匙了 新房里有一间他自己专用的很宽敞的房间 更让他高兴的是 妈妈昨天对他说 你的房间需要购买哪些物品 怎么布置 你说了算 只要不超过N元钱就行 今天一早金明就开始做预算 但是他想买的东西太多了 肯定会超过妈妈限定的N元 于是 他把每件物品规定了一个重要度 分为5等 用整数1 5表示 第5等最重要 他还从因特网上查到了每件物品的价格 都是整数元 他希望在不超过N元 可以等于N元 的前提下 使每件物品的价格与重要度的乘积的总和最大 设第j件物品的价格为v j 重要度为w j 共选中了k件物品 编号依次为j1 j2 jk 则所求的总和为 v j1 w j1 v j2 w j2 v jk w jk 其中 为乘号 请你帮助金明设计一个满足要求的购物单 5 开心的金明 输入文件 输入文件happy in的第1行 为两个正整数 用一个空格隔开 Nm 其中N 30000 表示总钱数 m 25 为希望购买物品的个数 从第2行到第m 1行 第j行给出了编号为j 1的物品的基本数据 每行有2个非负整数vp 其中v表示该物品的价格 v 10000 p表示该物品的重要度 1 5 输出文件 输出文件happy out只有一个正整数 为不超过总钱数的物品的价格与重要度乘积的总和的最大值 100000000 输入样例 1000580024005300540032002 输出样例 3900 6 金明的预算方案 金明今天很开心 家里购置的新房就要领钥匙了 新房里有一间金明自己专用的很宽敞的房间 更让他高兴的是 妈妈昨天对他说 你的房间需要购买哪些物品 怎么布置 你说了算 只要不超过N元钱就行 今天一早 金明就开始做预算了 他把想买的物品分为两类 主件与附件 附件是从属于某个主件的 下表就是一些主件与附件的例子 主件附件电脑打印机 扫描仪书柜图书书桌台灯 文具工作椅无如果要买归类为附件的物品 必须先买该附件所属的主件 每个主件可以有0个 1个或2个附件 附件不再有从属于自己的附件 金明想买的东西很多 肯定会超过妈妈限定的N元 于是 他把每件物品规定了一个重要度 分为5等 用整数1 5表示 第5等最重要 他还从因特网上查到了每件物品的价格 都是10元的整数倍 他希望在不超过N元 可以等于N元 的前提下 使每件物品的价格与重要度的乘积的总和最大 设第j件物品的价格为v j 重要度为w j 共选中了k件物品 编号依次为j1 j2 jk 则所求的总和为 v j1 w j1 v j2 w j2 v jk w jk 其中 为乘号 请你帮助金明设计一个满足要求的购物单 6 金明的预算方案 输入文件 输入文件的第1行 为两个正整数 用一个空格隔开 Nm其中N 0 表示该物品为附件 q是所属主件的编号 输出文件 输出文件只有一个正整数 为不超过总钱数的物品的价格与重要度乘积的总和的最大值 200000 6 金明的预算方案 输入样例 100058002040051300514003050020 输出样例 2200 转化为01背包问题考虑到每个主件最多只有两个附件 因此我们可以通过转化 把原问题转化为01背包问题来解决 在用01背包之前我们需要对输入数据进行处理 把每一种物品归类 即 把每一个主件和它的附件看作一类物品 处理好之后 我们就可以使用01背包算法了 在取某件物品时 我们只需要从以下四种方案中取最大的那种方案 只取主件 取主件 附件1 取主件 附件2 既主件 附件1 附件2 很容易得到如下状态转移方程 f i j max f i 1 j f i 1 j a i 0 a i 0 b i 0 f i 1 j a i 0 a i 1 a i 0 b i 0 a i 1 b i 1 f i 1 j a i 0 a i 2 a i 0 b i 0 a i 2 b i 2 f i 1 j a i 0 a i 1 a i 2 a i 0 b i 0 a i 1 b i 1 a i 2 b i 2 其中 f i j 表示用j元钱 买前i类物品 所得的最大值 a i 0 表示第i类物品主件的价格 a i 1 表示第i类物品第1个附件的价格 a i 2 表示第i类物品第2个附件的价格 b i 0 b i 1 b i 2 分别表示主件 第1个附件和第2个附件的重要度 f i 1 j 表示把j元钱全部投入前i 1类物品所得的最大值 即不取第i类物品这一方案 f i 1 j a i 0 a i 0 b i 0 表示只取第i类物品的主件这一方案 f i 1 j a i 0 a i 1 a i 0 b i 0 a i 1 b i 1 表示取第i类物品的主件和第 个附件这一方案 f i 1 j a i 0 a i 2 a i 0 b i 0 a i 2 b i 2 表示取第i类物品的主件和第2个附件这一方案 f i 1 j a i 0 a i 1 a i 2 a i 0 b i 0 a i 1 b i 1 a i 2 b i 2 则表示取第i类物品的主件和两个附件这一方案 vara array 1 60 0 3 ofinteger a数组用来存放每一类物品 a i 3 用来保存每类物品主件的编号b array 1 60 0 2 ofinteger f array 0 60 0 3200 ofinteger n m i s v p q j integer beginfillchar a sizeof a 0 fillchar b sizeof b 0 readln n m n ndiv10 s 0 fori 1tomdobeginreadln v p q 读入数据v vdiv10 优化 因为每个物品的价格是10的整数倍ifq 0thenbegin 主件inc s a s 0 v a s 3 i b s 0 p endelsebegin 是附件forj 1tosdo 此循环用来查找该附件的主件 找到后就退出循环ifa j 3 qthenbreak ifa j 1 0thenbegina j 1 v b j 1 p endelsebegina j 2 v b j 2 p end end end fillchar f sizeof f 0 m s 处理完输入数据后 s为共有多少类物品fori 1tomdo 对m类物品进行动态规划 枚举物品forj 0tondo 枚举状态begin 找最优的方案f i j f i 1 j 不取第i类物品if j a i 0 and f i j a i 0 a i 1 and f i j a i 0 a i 2 and f i j a i 0 a i 1 a i 2 and f i j f i 1 j a i 0 a i 1 a i 2 a i 0 b i 0 a i 1 b i 1 a i 2 b i 2 thenf i j f i 1 j a i 0 a i 1 a i 2 a i 0 b i 0 a i 1 b i 1 a i 2 b i 2 end writeln f m n 10 end 7 最长公共子序列 最长公共子序列 字符序列的子序列是指从给定字符序列中随意地 不一定连续 去掉若干个字符 可能一个也不去掉 后所形成的字符序列 令给定的字符序列X x0 x1 xm 1 序列Y y0 y1 yk 1 是X的子序列 存在X的一个严格递增下标序列 使得对所有的j 0 1 k 1 有xij yj 例如 X ABCBDAB Y BCDB 是X的一个子序列 给定两个序列A和B 称序列Z是A和B的公共子序列 是指Z同是A和B的子序列 问题要求已知两序列A和B的最长公共子序列 我们以 ACDEFACDE 与 CCACDEFCD 两个序列为例 研究求最长公共子序列的做法 不难发现 最长公共子序列与斜线的关系有关 我们要将上图的5连斜线与2连斜线接上 d 0 0 0 fori 1tondod i 0 0 forj 1tomdod 0 j 0 初始化fori 1tondoforj 1tomdoifs1 i s2 j thend i j d i 1 j 1 1elsebeginifd i 1 j d i j 1 thend i j d i 1 j elsed i j d i j 1 end 下面我们给出一个基本的程序段 8 回文词 题目描述 vijos1327 回文词是一种对称的字符串 也就是说 一个回文词 从左到右读和从右到左读得到的结果是一样的 任意给定一个字符串 通过插入若干字符 都可以变成一个回文词 你的任务是写一个程序 求出将给定字符串变成回文词所需插入的最少字符数 比如字符串 Ab3bd 在插入两个字符后可以变成一个回文词 dAb3bAd 或 Adb3bdA 然而 插入两个以下的字符无法使它变成一个回文词 输入格式 第一行包含一个整数N 表示给定字符串的长度 3 N 5000第二行是一个长度为N的字符串 字符串由大小写字母和数字构成 输出格式 一个整数 表示需要插入的最少字符数 样例输入 5Ab3bd 样例输出 2 谁能够用刚刚我们讲到的最长公共子序列来解决这道题呢 这道题看起来与最长公共子序列毫无关系 但是如果我们将字符串倒过来就会发现其中的精妙之处 在这里我们以样例Ab3bd为例S 原串 Ab3bdS1 倒序串 db3bALCSb3b我们实际需要添加的使其成为回文词的只有不在lcs中的A和d而已 下面谁能想到怎么写递推式 vara b array 1 1000 ofchar f array 0 1000 0 1000 oflongint n i j integer functionmax x y longint longint beginifx ythenexit x elseexit y end Beginreadln n fori 1tondobeginread a i b n i 1 a i 制作S2end fori 1tondo LCSforj 1tondoifa i b j thenf i j f i 1 j 1 1elsef i j max f i 1 j f i j 1 writeln n f n n 输出需要配对的字符数end 思考题 如果是3个字符串求最长公共子序列又该怎么做呢 9 区间dp 合并 意思就是将两个或多个部分进行整合 当然也可以反过来 也就是是将一个问题进行分解成两个或多个部分 特征 能将问题分解成为两两合并的形式求解 对整个问题设最优值 枚举合并点 将问题分解成为左右两个部分 最后将左右两个部分的最优值进行合并得到原问题的最优值 有点类似分治算法的解题思想 典型试题 整数划分 凸多边形划分 石子合并 多边形合并 能量项链等 10 整数划分 给出一个长度为n的数要在其中加m 1个乘号 分成m段这m段的乘积之和最大m n 20有T组数据 T 10000 10 整数划分 给出一个长度为n的数要在其中加m 1个乘号 分成m段这m段的乘积之和最大m n 20有T组数据 T 10000 10 整数划分 可以先预处理出原数第i到j段的数值A i j 是多少 这样转移就方便了 预处理也要尽量降低复杂度 F i j 表示把这个数前i位分成j段得到的最大乘积 F i j F k j 1 A k 1 i 1 k i n j m时间复杂度为O mn2 请大家想一想这道题的循环应该怎么写 11 石子合并 题目描述 在一个园形操场的四周摆放N堆石子 现要将石子有次序地合并成一堆 规定每次只能选相邻的2堆合并成新的一堆 并将新的一堆的石子数 记为该次合并的得分 试设计出1个算法 计算出将N堆石子合并成1堆的最小得分和最大得分 输入格式 数据的第1行试正整数N 1 N 100 表示有N堆石子 第2行有N个数 分别表示每堆石子的个数 输出格式 输出共2行 第1行为最小得分 第2行为最大得分 输入样例 44459 输出样例 4354 11 石子合并 这道题是不是和整数划分有很多相似之处 这也是一道区间dp题 但有一点非常不同 石子合并是在圆形操场 也就是说这不是一个线性的dp问题而是一个环形的dp问题 遇到这种题目我们又该如何去解决呢 从这道题目来看 它是一个环形的结构 因此我们可以把这个环从某个点分开 然后扩展成为两倍 从而更加方便的枚举各个区间 解决了回环往复的问题 这个处理方法还应用在usaco1 1破碎的项链 还有能量项链的解题之中 状态转移方程 f j p max f j k f k 1 p sum j p g j p min g j k g k 1 p sum j p 其中的sum数组表示两点之间的和 包括两点 最后请问大家在变成两倍后我们解存在哪里 我们只要找所有长度为n的区间内的最大值即可 varf g array 0 200 0 200 oflongint map array 0 200 oflongint n longint procedureinit vari longint beginfillchar f sizeof f 0 filldword g sizeof g 2 maxint 500 readln n fori 1tondobeginread map i map i n map i end fori 1to2 ndobeginf i i 0 g i i 0 end end functionsum a b longint longint vari longint beginsum 0 fori atobdoinc sum map i exit sum end functionmax a b longint longint beginifa bthenexit a elseexit b end functionmin a b longint longint beginifa bthenexit a elseexit b end proceduredp vari j k ans p ans1 longint beginans 0 ans1 maxlongint fori 1tondoforj 1to2 n i 1dobeginp i j fork jtop 1dobeginf j p max f j p f j k f k 1 p sum j p g j p min g j p g j k g k 1 p sum j p end end fori 1tondobegini