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
