Description

小 P 是个特么喜欢玩 MC 的孩纸......

小 P 在 MC 里有 \(n\) 个牧场, 自西向东呈一字形排列 (自西向东用 \(1 \ldots n\) 编号), 于是他就烦恼了: 为了控制这 \(n\) 个牧场, 他需要在某些牧场上面建立控制站, 其中满足 一下几个条件:

  1. 每个牧场上只能建立一个控制站, 每个控制站控制的牧场是它所在的牧场一直到它西边第一个控制站的所有牧场;
  2. 每个控制站西边第一个控制所在的牧场不被控制;
  3. 如果控制站西边不存在控制站, 那么它控制西边所有的牧场;
  4. 每个牧场被控制都需要一定的花费 (毕竟在控制站到牧场间修建道路是需要资源的嘛~) , 而且该花费等于它到控制它的控制站之间的牧场数目 (不包括自身, 但包括控制站所在 牧场) 乘上该牧场的放养量.

在第 \(i\) 个牧场建立控制站的花费是 \(a_i\), 每个牧场 \(i\) 的放养量是 \(b_i\), 理所当然, 小 P 需要总花费最小, 但是小 P 的智商有点不够用了, 所以这个最小总花费就由你来算出啦.

Input

第一行一个整数 \(n\) 表示牧场数目

第二行包括 \(n\) 个整数, 第 \(i\) 个整数表示 \(a_i\)

第三行包括 \(n\) 个整数, 第 \(i\) 个整数表示 \(b_i\)

Output

只有一行, 包括一个整数, 表示最小花费

Sample Input

4
2 4 2 4
3 1 4 2

Sample Output

9

Data Range

对于 100% 的数据,\(1 \leq n \leq 1000000\)

Explanation

首先正着推很麻烦对不对, 所以就反着推, 得到的是能省多少钱

所以就有:

\[f_i = f_j + \sum_{k=1}^{i} b_k \cdot (j - i) - a_i\]

然后就是 \(O(n^2)\) 的做法:


#include <iostream>
#include <cstdlib>
#include <cstdio>

using namespace std;
typedef long long lli;
const int maxn = 1000100;

int n;
lli a[maxn], b[maxn], pre_b[maxn];
lli dp[maxn];

int main(int argc, char** argv)
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%lld", &a[i]);
    for (int i = 1; i <= n; i++)
        scanf("%lld", &b[i]);
    for (int i = 1; i <= n; i++)
        pre_b[i] = pre_b[i - 1] + b[i];
    dp[n] = 0;
    for (int i = n - 1; i >= 1; i--)
        for (int j = n; j > i; j--)
            dp[i]= max(dp[i], dp[j] + pre_b[i] * (j - i) - a[i]);
    // Deducing dynamic programming result from total result
    lli sum = a[n], res = 0;
    for (int i = 1; i <= n; i++)
        sum += b[i] * (n - i);
    for (int i = 1; i <= n; i++)
        res = max(res, dp[i]);
    res = sum - res;
    printf("%lld\n", res);
    return 0;
}

现在考虑斜率优化, 我们发现对于任意的 \(i\), 其都可以表达为含有常数的一个式子. 例如 如果令 \(c_i = \sum_{k=1}^{i}\), 则有 \(f_i = f_j + c_i \cdot {j-i} - a_i\). 我们发现 可以构建这样一个平面直角坐标系, 横坐标为 \(i, j, \ldots\), 纵坐标为 \(f_i, f_j, \ldots\).

这样就一定有 \(c_j = \frac{dy}{dx}\), 对于成立的这样的 \(j\).

所以我们把不符合条件的点拿掉, 也就是维护一个上凸曲线. 这样维护的曲线可以保证时间复杂度在 \(O(n \log n)\) 以内.

终于有一次自己弄懂了斜率优化~

Source Code


#include <iostream>
#include <cstdlib>
#include <cstdio>

using namespace std;
typedef long long lli;
typedef long double llf;
const int maxn = 1000100;

int n;
lli a[maxn], b[maxn], pre_b[maxn];
lli dp[maxn];
int deque[maxn];

llf slope(int j, int k) {
    return llf(dp[k] - dp[j]) / llf(j - k); }

int main(int argc, char** argv)
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%lld", &a[i]);
    for (int i = 1; i <= n; i++)
        scanf("%lld", &b[i]);
    for (int i = 1; i <= n; i++)
        pre_b[i] = pre_b[i - 1] + b[i];
    // Working with deque
    dp[n] = 0;
    int l = 1, r = 0;
    deque[++r] = n;
    // Maintain upper convex hull
    for (int i = n - 1; i >= 1; i--) {
        dp[i] = 0;
        while (l < r && slope(deque[l], deque[l + 1]) > pre_b[i])
            l += 1; // deque.pop_front();
        int j = deque[l];
        dp[i] = dp[j] + pre_b[i] * (j - i) - a[i];
        while (r > l && slope(deque[r], i) > slope(deque[r - 1], deque[r]))
            r -= 1; // deque.pop_back();
        deque[++r] = i;
    }
    // Deducing dynamic programming result from total result
    lli sum = a[n], res = 0;
    for (int i = 1; i <= n; i++)
        sum += b[i] * (n - i);
    for (int i = 1; i <= n; i++)
        res = max(res, dp[i]);
    res = sum - res;
    printf("%lld\n", res);
    return 0;
}