SkyWT / 博客 / 动态规划经典题目(一):石子合并

动态规划经典题目(一):石子合并

2018 年 1 月 21 日 12:08


动态规划(Dynamic Programming),简称DP,是用于求解决策过程中的最优化数学方法,不仅用于编程领域,也用于管理学、经济学、生物学(具体这三个地方怎么用就不关我们事了)。作为NOIP竞赛的每年必考题型,动态规划是很重要的!!!

石子合并(NOI1995)(区间DP)

洛谷题目提交网址:石子合并
  • 问题描述

在一个圆形操场的四周摆放N堆石子,现要将石子有次序地合并成一堆。规定每次只能选相邻的2堆合并成新的一堆,并将新的一堆的石子数记为该次合并的得分。试设计出一个算法,计算出将N堆石子合并成1堆的最小得分和最大得分。
  • 输入文件

输入第一行为 n(n≤100),表示有 n 堆石子。第二行为 n 个用空格隔开的整数,依次表示这 n 堆石子的石子数量。( ≤1000)
  • 输出文件

输出共 2 行; 第 1 行为将 n 堆石子合并成一堆的最小得分; 第 2 行为将 n 堆石子合并成一堆的最大得分。
  • 输入样例

3
1 2 3
  • 输出样例

9
11
  • 问题分析

一看到这题,我第一个想到的就是合并果子这道题。这两题的确很像,但是仔细看就发现他们存在的很明显的一个不同是:这题只能合并相邻两堆,而合并果子那题可以随便跳两堆合并。那么这题可以用贪心吗?显然有很多很多很多的反例,以求最小为例,比如有六堆石子,分别是3 4 6 5 4 2:
贪心:3 4 6 5 4 2
5 4 6 5 4 (+5)
9 6 5 4 (+9)
9 6 9 (+9)
15 9 (+15)
24 (+24)
Total:62
正解:3 4 6 5 4 2
7 6 5 4 2 (+7)
7 6 5 6 (+6)
7 6 11 (+11)
13 11 (+11)
24 (+24)
Total:59
所以贪心的方法肯定是不行的。再回来看看这题,发现首先决策不是按照一堆一堆来的,也就是说没法刷线性的DP;一个决策可以划分成很多子决策(也就是说所有的合并可以是1~i的合并得分+i+1~n的合并得分),那么不显然是区间DP嘛!

首先处理环的问题。一般处理环的问题的方法就是:复制一份,放到序列尾,这样就把环变成长度为原来两倍的链了。例如:

环:1 2 3 4
链:1 2 3 4 1 2 3 4
接下来,DP正式部分:定义F[i][j]为从i到j一段石子合并的最优解。那么自然会想到在i~j-1之间枚举k(为什么是j-1不是j?看转移方程就知道了),为了方便我们先造出前缀和sum,转移方程:
F[i][j]=max/min(F[i][k],F[k+1][j])+sum[j]-sum[i-1];
复杂度:O(N³)。

算是挺简单的一题。


暂无评论


发表新的评论

所有评论都将经过博主审核。请勿填写无意义邮箱或发表无关评论、广告等,否则会被视为垃圾评论。

提交评论即表明你同意本网站使用 Cookie,并允许本站在后台记录你的邮箱、IP 地址等必要信息。这些信息不会被透露给其他用户。(提交一次评论后,本提示将不再展示)