What's in 幸福de小窝...?
lhr0909 · 2007-07-25
<< 分书 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