数学

it2022-09-23  3

数学

时间限制: 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; }

转载于:https://www.cnblogs.com/LLppdd/p/8946813.html

最新回复(0)