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

动态规划(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³)。

算是挺简单的一题。

本文采用 BY-NC-SA 4.0 协议,欢迎转载。如有错误欢迎指出。
本文链接: https://skywt.cn/posts/stone/

发表评论

电子邮件地址不会被公开。 必填项已用*标注

相关文章

开始在上面输入您的搜索词,然后按回车进行搜索。按ESC取消。