51Nod 1022. 石子归并 V2(四边形不等式优化)

日付: 10月 14, 2018

[石子归并 V2问题 - 51Nod](https://www.51nod.com/onlineJudge/questionCode.html#!problemId=1022)

## Problem
一堆石子摆成**环**，每次只能选相邻的2堆石子合并成新的一堆，并将新的一堆石子数记为该次合并的代价。求全部合并成一堆最小代价。

数据范围：$2 \le N \le 1000, 1 \le A[i] \le 10000$

## Solution
如果不是一个环而是一行的话，很容易写出区间dp转移方程$F(i,j) = min(F(i,k)+F(k+1,j)) + Sum(i,j), \quad i \le k < j$，但是复杂度是$O(N^3)$，因此需要优化。

对于这类转移方程，可以使用四边形不等式优化 [Quadrangle Optimization](https://kongroo.blogspot.com/2018/10/quadrangle-optimization.html)

$Sum$满足区间包含的单调性(区间和一定不小于其子区间的和)，以及四边形不等式(交叉不大于包含)。因此$F$也满足四边形不等式，决策$S(i,j)$($[i,j]$区间最优的$k$)具有单调性，即$S(i,j-1) \le S(i,j) \le S(i+1,j)$，因此在枚举$k$时只需枚举$[S(i,j-1),S(i+1,j)]$，复杂度降为$O(N^2)$

然后再考虑环的情况，一般解决环问题的思路是把数组重复2次，本题也可以这样解决。在重复2次的新数组$A$上使用四边形优化dp算出所有的$F(i,j)$，答案就是 $min F(i,i+n-1), \quad 1\le i \le n$

## Code
```c++
#include <bits/stdc++.h>
using namespace std;

// 51Nod. 1022
int F[2002][2002], S[2002][2002];
int main() {
    int n;
    scanf("%d", &n);
    vector<int> A(n + 1);
    for (int i = 1; i <= n; i++) scanf("%d", &A[i]);
    A.insert(A.end(), A.begin() + 1, A.end());
    for (int i = 1; i <= n * 2; i++) A[i] += A[i - 1];
    memset(F, 10, sizeof F);
    for (int i = 1; i <= n * 2; i++) S[i][i] = i, F[i][i] = 0;
    for (int len = 2; len <= n * 2; len++) {
        for (int i = 1; i + len - 1 <= n * 2; i++) {
            int j = i + len - 1;
            for (int k = S[i][j - 1]; k < j && k <= S[i + 1][j]; k++) {
                int tmp = F[i][k] + F[k + 1][j];
                if (tmp < F[i][j]) F[i][j] = tmp, S[i][j] = k;
            }
            F[i][j] += A[j] - A[i - 1];
        }
    }
    auto ans = INT_MAX;
    for (int i = 1; i <= n; i++) ans = min(ans, F[i][i + n - 1]);
    printf("%d\n", ans);
    return 0;
}
```

KONGROOの基地

このブログを検索

51Nod 1022. 石子归并 V2(四边形不等式优化)

コメント

コメントを投稿