hdu 3506 Monkey Party 区间dp + 四边形不等式优化

http://acm.hdu.edu.cn/showproblem.php?pid=3506

四边行不等式:http://baike.baidu.com/link?url=lHOFq_58V-Qpz_nTDz7pP9xCeHnd062vNwVT830z4_aQoZxsCcRtac6CLzbPYLNImi5QAjF2k9ydjqdFf7wlh29GJffeyG8rUh-Y1c3xWRi0AKFNKSrtj3ZY7mtdp9n5W7M6BBjoINA-DdplWWEPSK#1

dp[i][j]表示第i--j堆合并成一堆的时候，所需的最小花费。

然后根据以前的，dp[i][j] = dp[i][k] + dp[k + 1][j] + cost

那么我就要去找那个位置k。

能够证明的就是，cost满足四边形不等式。

我们设w[i][j]表示第i--j个数的和。

引用一下：

当函数w(i,j)满足 w(a,c)+w(b,d) <= w(b,c)+w(a,d) 且a<=b< c <=d 时，我们称w(i,j)满足四边形不等式。。

关于这个，其实是绝对相等的，不是大于。

证明如下。设sum[i]表示1--i的和

那么上面的不等式变成：

左边:sum[c] - sum[a - 1] + sum[d] - sum[b - 1]

右边:sum[d] - sum[a - 1] + sum[c] - sum[b - 1];

是相等的。所以满足条件

当函数w(i, j)满足w(i', j) <= w(i, j'); i <= i' < j <= j' 时，称w关于关于区间包含关系单调。

这个很容易，画个图，很明显

于是有以下三个定理

定理一：如果w同时满足四边形不等式和决策单调性 ,则d也满足四边形不等式
定理二：当定理一的条件满足时，让d[i,j]取最小值的k为K[i,j]，则K[i,j-1]<=K[i,j]<=K[i+1,j]
定理三：w为凸当且仅当w[i,j]+w[i+1,j+1]<=w[i+1,j]+w[i,j+1]

由定理三知判断w是否为凸即判断 w[i,j+1]-w[i,j]的值随着i的增加是否递减
于是求K值的时候K[i,j]只和K[i+1,j] 和 K[i,j-1]有关，所以可以以i-j递增为顺序递推各个状态值最终求得结果将O(n^3)转为O(n^2)

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cmath>

#include <algorithm>

#include <assert.h>

#define IOS ios::sync_with_stdio(false)

using namespace std;

#define inf (0x3f3f3f3f)

typedef long long int LL;

#include <iostream>

#include <sstream>

#include <vector>

#include <set>

#include <map>

#include <queue>

#include <string>

int n;

const int maxn = 2e3 + ;

int dp[maxn][maxn];

int s[maxn][maxn];

int sum[maxn];

int a[maxn];

void work() {

    for (int i = ; i <= n; ++i) {

        scanf("%d", &a[i]);

        a[i + n] = a[i];

    }

    n *= ;

    for (int i = ; i <= n; ++i) {

        dp[i][i] = ;

        s[i][i] = i;

        sum[i] = sum[i - ] + a[i];

    }

    for (int dis = ; dis <= n - ; ++dis) {

        for (int be = ; be + dis <= n; ++be) {

            int en = be + dis;

            int tk = s[be][en];

            dp[be][en] = inf;

            for (int k = s[be][en - ]; k <= s[be + ][en]; ++k) {

                if (k +  > en) break;

                int add = dp[be][k] + dp[k + ][en] + sum[en] - sum[be - ];

                if (dp[be][en] > add) {

                    dp[be][en] = add;

                    tk = k;

                }

            }

            s[be][en] = tk;

        }

    }

    int ans = inf;

    for (int i = ; i <= n / ; ++i) {

        ans = min(ans, dp[i][i + n /  - ]);

    }

    cout << ans << endl;

}

int main() {

#ifdef local

    freopen("data.txt", "r", stdin);

//    freopen("data.txt", "w", stdout);

#endif

    while (scanf("%d", &n) != EOF) work();

    return ;

}

今天看得lrj的书中介绍的四边形优化做个笔记，加强理解

最有代价用d[i,j]表示
d[i,j]=min{d[i,k-1]+d[k+1,j]}+w[i,j]
其中w[i,j]=sum[i,j]
四边形不等式
     w[a,c]+w[b,d]<=w[b,c]+w[a,d](a<b<c<d) 就称其满足凸四边形不等式
决策单调性
     w[i,j]<=w[i',j']   ([i,j]属于[i',j']) 既 i'<=i<j<=j'

http://www.cnblogs.com/zxndgv/archive/2011/08/02/2125242.html

巴特西

hdu 3506 Monkey Party 区间dp + 四边形不等式优化

最新文章

热门文章