What's in 幸福de小窝...?

<< 分书 DFS 深度优先搜索 | 首 页 | 数字三角形 dp 动态规划 >> 石子合并 dp 动态规划 - [ 信息学奥赛 ] 2007-07-25 Tag: dp 动态规划 算法 在一个园形操场的四周摆放N堆石子(N≤100),现要将石子有次序地合并成一堆。规定每次只能选相邻的两堆合并成新的一堆,并将新的一堆的石子数,记为该次合并的得分。 编一程序,由文件读入堆数N及每堆的石子数(≤20), ①选择一种合并石子的方案,使得做N-1次合并,得分的总和最小; ②选择一种合并石子的方案,使得做N-1次合并,得分的总和最大。 例如,所示的4堆石子,每堆石子数(从最上面的一堆数起,顺时针数)依次为4594。 则3次合并得分总和最小的方案:8+13+22=43 得分最大的方案为:14+18+22=54 输入数据: 文件名由键盘输入,该文件内容为: 第一行为石子堆数N; 第二行为每堆的石子数,每两个数之间用一个空格符分隔。 输出数据: 输出文件名为output.txt 从第1至第N行为得分最小的合并方案。第N+1行是空行。从第N+2行到第2N+1行是得分最大合并方案。 每种合并方案用N行表示,其中第i行(1≤i≤N)表示第i 次合并前各堆的石子数(依顺时针次序输出,哪一堆先输出均可)。 要求将待合并的两堆石子数以相应的负数表示,以便标识。 输入输出范例: 输入文件内容: 4 4 59 4 输出文件内容: -4 5 9 -4 -8-5 9 -13 -9 22 4 -5 -9 4 4 -14 -4 -4-18 22 写到想吐... 首先设置一个函数... f(i,j)表示从第i堆开始数j堆石头所得的最优解... 由于大于等于3堆的时候,石头往前分解就有多种情况,所以要把他分开来枚举... 再设置一个函数... c(i,j)表示把刚才那坨石头f(i,j)分解成两坨的时候,其中一坨的石头堆数... 然后就可以写递推方程... f(i,j)=相邻两个相加 (j=2) c(i,j)=1 (j=2) f(i,j)=最优(max或min){f(i,k)+f(t,j-k)+sum(i,j)} (j>=3) c(i,j)=k (当f(i,j)最优的时候) 说明一下... k是情况数(也就是石头分成两坨的情况)要枚举的... sum(i,j)是从第i堆开始数j堆石头的总数(可以搞一个表,也可以用函数做...) t要分情况讨论(因为要考虑循环问题) 所以if i+k>n then t=(i+k)mod n else t=i+k 接下来就是痛苦的输出了...我的方法是,用递归根据c(i,j)追根溯源,找到堆叠的次序...然后把次序压到堆栈中,到时候取出来...唉...从早上十点写到下午三点啊...唉... 庆幸的是,现在起码搞懂了... lhr0909 @ 21:08:49 | 引用 0 | 编辑 评论 发表评论 姓名: E-mail: 地址:

原始快照:web.archive.org