动态规划(Dynamic Programming),简称DP,是用于求解决策过程中的最优化数学方法,不仅用于编程领域,也用于管理学、经济学、生物学(具体这三个地方怎么用就不关我们事了)。作为NOIP竞赛的每年必考题型,动态规划是很重要的!!!
石子合并(NOI1995)(区间DP)
洛谷题目提交网址:石子合并-
问题描述
-
输入文件
-
输出文件
-
输入样例
3 1 2 3
-
输出样例
9 11
-
问题分析
贪心: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³)。
算是挺简单的一题。