11061: 【原1061】小M的服务器

题目

题目描述

author: 寿鹤鸣原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1061

Description

小M需要将一个文件复制到n个服务器上，这些服务器的编号为S1, S2, …, Sn。

首先，小M可以选择一些服务器，直接把文件复制到它们中；将文件复制到服务器Si上，需要花费ci > 0的置放费用。

对于没有直接被复制文件的服务器Si来说，它依次向后检查Si+1, Si+2, …直到找到一台服务器Sj：Sj中的文件是通过直接复制得到的，于是Si从Sj处间接复制得到该文件，这种复制方式的读取费用是j-i（注意j>i）。

另外，Sn中的文件必须是通过直接复制得到的，因为它不可能间接的通过别的服务器进行复制。我们设计一种复制方案，即对每一台服务器确定它是通过直接还是间接的方式进行复制（Sn只能通过直接方式），最终使每一台服务器都得到文件，且总花费最小。

Input Format

第一行有一个整数n，表示服务器的数目。第二行有n个整数，顺数第i个表示ci：在Si上直接复制文件的费用。

Output Format

只包含一个整数，即最少需要花费的费用。

Hint

60%的数据中，\(1 \leq n \leq 1000\)

100%的数据中，\(1 \leq n \leq 1000000\)

80%的数据中， \(1 \leq ci \leq 50\)

100%的数据中，\(1 \leq ci \leq 1000000000\)

最终结果可能较大，请注意选择适当的数据类型进行计算。

Sample Input

10
2 3 1 5 4 5 6 3 1 2

Sample Output

FineArtz's solution

/* 小M的服务器 */
#include <iostream>
using namespace std;

const long long INF = 131313131313131313LL;

long long f[1000005], c[1000005];
long long q[1000005], front = 1, rear = 1;

inline double g(long long j, long long k){
    return (2 * (f[j] - f[k]) + j * (j - 1) - k * (k - 1)) * 0.5 / (j - k);
}

int main(){
    int n;
    cin >> n;
    c[0] = 0;
    for (int i = 1; i <= n; ++i)
        cin >> c[i];
    f[n] = c[n];
    q[front] = n;
    for (int i = n - 1; i >= 0; --i){
        while (front < rear && g(q[front], q[front + 1]) > i)
            ++front;
        f[i] = f[q[front]] + (q[front] - i) * (q[front] - i - 1) / 2 + c[i];
        while (front < rear && g(q[rear - 1], q[rear]) < g(q[rear], i))
            --rear;
        q[++rear] = i;
    }
    cout << f[0] << endl;
    return 0;
}