描述 Description

某一天在网上闲逛的玖君不小心发现了TYVJ，就立刻被TYVJ吸引住了，果断驻扎下来。玖君决定按照顺序来切题，因为离复赛越来越近了，所以他希望能够用最短时间AC掉前面N道题目，完成第i道题目玖君需要花费t[i]个单位的代价。玖君做题有个特点，他喜欢看完几道题后，一次把几道题的代码写完。如果玖君决定一次写完从编号L到编号R的题目，那么他完成这些题目的总代价等于编号L到R题目的代价之和与R之积，即SUM{t[L..R]} R。此外每道题在被切之前都会等待被切，等待的时间，也被算在代价里面，对于每个第k次被切的题，在它被切之前的等待代价为(k-1)S。综上，切完N道题的总代价=第1次切题的代价+第2次切题的代价+…+第k次切题的代价+每道题的等待代价。现在我们想知道玖君切完这N道题目的最小代价。

输入格式 InputFormat

第1行：2个用空格分开的整数N, S
第2行：N个用空格分开的整数，分别表示t[1]到t[N]
输出格式 OutputFormat

第1行：1个整数，表示玖君完成N道题的最小代价
样例输入 SampleInput [复制数据]

4 7
8 1 7 6
样例输出 SampleOutput [复制数据]

79
数据范围和注释 Hint

[样例解释]
第1次切1、2、3题：代价为48
第2次切4题：代价为24
其中每道题的等待时间代价为:0,0,0,7
共计48 + 24 + 7 = 79

[数据范围]
对于70%的数据，1 <= N <= 3000
对于100%的数据，1 <= N <= 30000
对于100%的数据，1 <= S,t[i] <= 100

Dp，然后先求前缀和数组，方便后面用到，设f[i]表示刷完前i个题所花费的最小代价，然后一个比较容易想到的方程就是

  • f[i]=min{f[j]+(sum[i]-sum[j])i+(n-i)S|0<=j<i} //shiugaosuyixiawo(n-i)*sshisuanfeiyongtiqianjisuanma?

然后这个显然当N＝30000时是不行的，会T，然后就发现，设用k更新i比用j更优，则

  • f[k] + (sum[i]-sum[k]) i + (n-i)s >=f[j] + (sum[i]-sum[j]) i + (n-i)s
  • (f[k]-f[j])/(sum[k]-sum[j])<=i

当满足这个条件时，k优于j ，然后就维护一个队列就行了，这个是所谓的斜率优化？还是得好好消化啊，dp水平太次了我。。。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <iostream>
#include <cstdio>
#include <cmath>

using namespace std;

typedef long long LL;

const int MN = 30010;

LL n, s;
LL f[MN];
LL sum[MN];
int q[MN];

double grad(int j, int k) {
    return ((f[k]-f[j])*1.0 / (sum[k]-sum[j]));
}

int main() {
    cin >> n >> s;
    for (int i = 1; i <= n; i++) {
        scanf("%lld", &sum[i]);
        sum[i] += sum[i-1];
    }
    int h = 1, t = 1;
    f[0] = 0;
    for (int i = 1; i <= n; i++) {
        while ((h < t) && (grad(q[h], q[h+1]) <= i)) ++h;
        f[i] = f[q[h]] + (sum[i]-sum[q[h]])*i + (n-i)*s;
        while ((h < t) && (grad(q[t-1], q[t]) >= grad(q[t], i))) --t;
        q[++t] = i;
    }
    cout << f[n] << endl;
    return 0;
}