斜率优化Tag ArchiveSubscribe

题目地址

题意是说有n座山，每座山之间距离不同为di，p个饲养员，m只猫。每只猫会在Hi座山上，在Ti时间等待饲养。饲养员只能从1走到n不能停留，问怎么规划饲养员的出发时间才能使得等待时间最少。饲养员的出发时间可以为负。

规定 sum 代表前缀和。

对于某只猫 i 来说。如果饲养员在时间 t 出发，他要走 sumD[i] 的距离，那么这只猫的等待时间 W = t + sumD[i] – T[i] 。由此如果设 A[i] = T[i] – sumD[i] 。那么饲养员从时间 t 出发每只猫 i 的等待时间就是 t – A[i]

把 A 从小到大排序，由于 t – A[i] 不能是负数，所以每个饲养员一定从最开始往后带走连续的若干只猫而且排序的数组中最后一只一定等待时间为 0 。

设 f[ i , j ] 为前 i 个饲养员带走了前 j 只猫。那么第 i 个饲养员肯定从 A[j] 时间出发，带走的猫等待时间为\sum_{p=k+1}^{j}A_j-A{p}=A_j \times(j-k)-sumA[j]+sumA[k]设其为C。

那么f[i][j] = min(f[i – 1][k] + C);

i j k 三层循环，把 i 看作不变量，对 j k 做斜率优化。同时由于每次只用到了i – 1的状态，所以可以把 … Read the rest

题目传送门
官方题解
题意是说找到一个连续子段，使得\sum_{i}^{j}a_i \times i最大，也就是说每个数要乘上自己在子段里的位置。

官方题解就是说，令f[i]表示前i个数字的答案。f_{i}=\max_{j=0}^{i-1} (\sum_{k=j+1}^{i}a_k \times {(k-j)})这样每个a就可以和自己对应的坐标相乘，而j又是固定的，所以可以直接用前缀和把题目简化掉。

要截距最大化，斜率不单调，维护整个上突壳，在上突壳上二分找左边斜率小于当前，右边斜率大于当前的点。注意答案的初始化要为负数，因为答案可能为负。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=2e5+233;
ll a[maxn],b[maxn],f[maxn];
int q[maxn];
int l=1,r=1;
int n;
int brf(int k)
{
    if(l == r) return q[l];
    int L=l,R=r;
    while(L<R)
    {
        int mid=(L+R)>>1;
        if(b[q[mid + 1]] * q[mid + 1] - a[q[mid + 1]] - b[q[mid]] * q[mid] + a[q[mid]] 
            >= b[k] * (q[mid + 1] - q[mid])) L = mid + 1;
        else R