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)

证明可见 [ 动态规划加速原理之四边形不等式 ](http://wenku.baidu.com/link?url=fAi5jF00X4jQ-UfbH9YKA
btUK688rOmjIXX5cU3IQjplOj9VKyllGPpBwt_E5wlONNVPw7GhkmsmFHcQGvr02gHT21OtLp78rHH
zqPkBRgO)

显然,由上述定理,本来我们的第三重循环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四边形不等式优化)
https://shiyi.threebody.xyz/posts/48436.html
作者
Yi Shi
发布于
2015年12月3日
许可协议