Codeforces 643C Levels and Regions 斜率优化dp

把dp方程列出来，把所有东西拆成前缀的形式，就能看出可以斜率优化啦。
#include<bits/stdc++.h>

#define LL long long

#define fi first

#define se second

#define mk make_pair

#define PLL pair<LL, LL>

#define PLI pair<LL, int>

#define PII pair<int, int>

#define SZ(x) ((int)x.size())

#define ull unsigned long long

using namespace std;

const int N = 2e5 + ;

const int inf = 0x3f3f3f3f;

const LL INF = 0x3f3f3f3f3f3f3f3f;

const int mod = 1e9 + ;

const double eps = 1e-;

const double PI = acos(-);

int n, k, be, ed, que[N];

double sum[N], prefix[N], dp[N][], t[N];

double calc(int k, int j, int c) {

    return ((dp[j][c] + sum[j] * prefix[j]) - (dp[k][c] + sum[k] * prefix[k])) / (sum[j] - sum[k]);

}

int main() {

    be = , ed = ;

    scanf("%d%d", &n, &k);

    for(int i = ; i <= n; i++) scanf("%lf", &t[i]);

    for(int i = ; i <= n; i++) prefix[i] = prefix[i - ] +  / t[i];

    for(int i = ; i <= n; i++) sum[i] = sum[i - ] + t[i];

    dp[][] = ;

    que[++ed] = ;

    for(int j = ; j <= k; j++) {

        int p = j - ;

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

            while(j >  && p < i) {

                while(ed - be +  >=  && calc(que[ed-], que[ed], j-) > calc(que[ed], p, j-)) ed--;

                que[++ed] = p;

                p++;

            }

            while(ed - be +  >=  && calc(que[be], que[be+], j-) < prefix[i]) be++;

            int who = que[be];

            dp[i][j] = dp[who][j - ] - sum[who] * (prefix[i] - prefix[who]);

        }

        be = ; ed = ;

    }

    double ans = dp[n][k];

    for(int i = ; i <= n; i++) ans += sum[i] / t[i];

    printf("%.12f\n", ans);

    return ;

}

/*

*/