本文主要是介绍51Nod 1022 石子归并 V2 (划分型dp四边形不等式优化)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
石子归并以前做过好几次，是经典划分型dp题之一，一直用的O(n3)的正常dp方法，也从未想过该怎么去优化它。
直到昨天做这道题，n的范围由往常的100改为了1000，老方法 一直超时，苦不堪言，搜到有个四边形不等式的优化方法，看帖子，画式子，拉着学长帮忙推导，总算是大概弄明白了一点。
dp(i,j) = min(dp(i,k)+dp(k+1,j)) + w(i,j);(i < j, i<=k<j)
dp(i,j) = MAX;(i>j)
dp(i,j) = 0;(i=j)
上式在动态规划的状态转移方程中是很常见的，对于上式中的w(i,j)
如果符合w(i`,j) <= w(i,j`) i<i`<j<j` 那么我们称函数w满足关于区间包含的单调性
如果符合w(i,j)+w(i`,j`) <= w(i`,j)+w(i,j`) 那么我们称函数w满足四边形不等式
那么，有两个定理：(图片取自http://blog.csdn.net/shiwei408/article/details/8791011)
证明可见 动态规划加速原理之四边形不等式
显然，由上述定理，本来我们的第三重循环k的范围是由i<=k<j
现在可以缩至s[i][j-1]<=k<=s[i+1][j]，一下就从O(n3)优化至O(n2)了;
下面看题
1022 石子归并 V2 
基准时间限制：1 秒 空间限制：131072 KB 分值: 160 难度：6级算法题
N堆石子摆成一个环。现要将石子有次序地合并成一堆。规定每次只能选相邻的2堆石子合并成新的一堆，并将新的一堆石子数记为该次合并的代价。计算将N堆石子合并成一堆的最小代价。
例如： 1 2 3 4，有不少合并方法
1 2 3 4 => 3 3 4(3) => 6 4(9) => 10(19)
1 2 3 4 => 1 5 4(5) => 1 9(14) => 10(24)
1 2 3 4 => 1 2 7(7) => 3 7(10) => 10(20)
括号里面为总代价可以看出，第一种方法的代价最低，现在给出n堆石子的数量，计算最小合并代价。
Input
第1行：N（2 <= N <= 1000) 第2 - N + 1：N堆石子的数量（1 <= A[i] <= 10000)
Output
输出最小合并代价
Input示例
4 1 2 3 4
Output示例
19
跟我们之前做过的石子归并有两个区别，一个是n的范围变为了1000，3重循环已无用，需要优化，上已道明。
另一个区别就是从往常的线型变为了环形，这个通常有三种方法可以处理。
1. 循环变量自增由 i++ 改为 i = (i+1)%n 利用取余操作实现由n-1至0的迭代
2. 构造next数组，模拟链表指向
3. 将环扩展为一维线性 即 环变为 a[0],a[1],...a[n-1],a[n-2],...a[1],a[0] 注意扩展后数组长度为2*n-1(a[n-1]只有一次)
这里本人用的第三种方法，见代码
#include<iostream>
#include<string.h>
#include<algorithm>
#include<stdlib.h>
#include<stdio.h>using namespace std;const int N = 2009;
int n,f[N][N]={0},a[N][N]={0};
int s[N][N];int main()
{memset(f,1,sizeof(f));scanf("%d",&n);for(int i=0;i<n;i++){scanf("%d",&a[i][i]);a[n+i][n+i] = a[i][i];}for(int i=0;i<n*2;i++){s[i][i] = i;f[i][i] = 0;}for(int i=0;i<n*2-1;i++)for(int j=i+1;j<n*2-1;j++)a[i][j] = a[i][j-1] + a[j][j];for(int l=1;l<n;l++){for(int i=0;i+l<n*2-1;i++){int j = i+l;for(int k=s[i][j-1];k<=s[i+1][j];k++){if(f[i][j] > a[i][j]+f[i][k]+f[k+1][j]){f[i][j] = a[i][j]+f[i][k]+f[k+1][j];s[i][j] = k;}}}}int ans = f[0][n-1];for(int i=1;i<n;i++)if(ans > f[i][i+n-1])ans = f[i][i+n-1];printf("%d\n",ans);return 0;
}这篇关于51Nod 1022 石子归并 V2 (划分型dp四边形不等式优化)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
