博客

数学

时间限制: 5000 ms 内存限制: 131072 KB

题目描述

Shy 有一个长度为 n 的数组 a[i]，让你把这个数组分成 k 份（每份包含至少一个元素，且每份中的元素连续）。假设其中一份长这个样子，b[1], b[2],…,b[m]，那么他的价值是b[1]/b[1]+(b[1]+b[2])/b[2]+…+(b[1]+b[2]+…+b[m])/b[m]，求在所有的合法的划分中，最小的价值和是多少。

输入

第一行两个整数 n，k 表示数组长度和分成的份数；

第二行为n个整数。

输出

输出一个数表示答案。（要求与标准答案的绝对或相对误差不差过 1/10000）。

输入样例

4 2

100 3 5 7

输出样例

5.7428571429

数据规模

对于 30%的数据，1≤n≤1000;

对于 100%的数据，1≤n≤200000，1≤k≤min(50,n)，1≤a[i]≤100000。

这是一道斜率优化。。。。

我个人觉得w大爷会毒瘤学弟学妹，所以记一下。。。。

疯狂推公式吧。。。

正确姿势如下：

写方程

凑乘法

找单调

为了完成上面的操作，疯狂预处理吧！（遇到求和就预处理233）

#include<bits/stdc++.h>
using namespace std;
struct lpl{
    double x, y;
}lin;
const int maxn = 2e5 + 5;
double R[maxn], D[maxn], S[maxn], dp[55][maxn];
int n, k, ini[maxn], l[55], r[55];
lpl getans[55][maxn];

inline double slop(lpl A, lpl B) {return (double)(A.y - B.y) / (A.x - B.x);}

inline void putit()
{
    scanf("%d%d", &n, &k); 
    for(int i = 1; i <= n; ++i) scanf("%d", &ini[i]);
    for(int i = 1; i <= n; ++i){
        S[i] = S[i - 1] + ini[i];
        R[i] = R[i - 1] + S[i] / ini[i];
        D[i] = D[i - 1] + (double)(1.0) / ini[i];
    }
}

inline void workk()
{
    for(int i = 1; i <= k; ++i) l[i] = 1;
    for(int i = 1; i <= n; ++i){
        dp[1][i] = dp[1][i - 1] + S[i] / ini[i];    
        lin.x = S[i]; lin.y = dp[1][i] + D[i] * S[i] - R[i];
        while(l[1] < r[1] && slop(getans[1][r[1] - 1], getans[1][r[1]]) > slop(lin, getans[1][r[1]])) r[1]--;
        r[1]++; getans[1][r[1]] = lin; 
    }
    for(int i = 2; i <= k; ++i){
        for(int j = i; j <= n; ++j){
            while(l[i - 1] < r[i - 1] && slop(getans[i - 1][l[i - 1]], getans[i - 1][l[i - 1] + 1]) < D[j]) l[i - 1]++;
            dp[i][j] = getans[i - 1][l[i - 1]].y - D[j] * getans[i - 1][l[i - 1]].x + R[j];
            lin.x = S[j]; lin.y = dp[i][j] + D[j] * S[j] - R[j];
            while(l[i] < r[i] && slop(getans[i][r[i] - 1], getans[i][r[i]]) > slop(lin, getans[i][r[i]])) r[i]--;
            r[i]++; getans[i][r[i]] = lin;
        }       
    }

}

int main()
{
    putit();
    workk();
    printf("%.10lf", dp[k][n]);
    return 0;
}