题目地址

题意是说有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的状态，所以可以把 i 层空间滚动起来。时间复杂度PM，空间复杂度2M

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+233;
typedef long long ll;
int n,m,p;
int d[maxn];
ll a[maxn],f[maxn],g[maxn],q[maxn],s[maxn];
int main()
{
    scanf("%d%d%d",&n,&m,&p);
    for(int i=2;i<=n;i++) scanf("%d",&d[i]),d[i]+=d[i-1];
    for(int i=1;i<=m;i++)
    {
        int h,t;
        scanf("%d%d",&h,&t);
        a[i]=t-d[h];
    }
    sort(a+1,a+1+m);
    for(int i=1;i<=m;i++) s[i]=s[i-1]+a[i];
    memset(f,0x3f,sizeof f);
    f[0]=0;q[1]=0;
    for(int i=1;i<=p;i++)
    {
        memcpy(g,f,sizeof f);
        memset(f,0x3f,sizeof f);
        //f[0]=0;
        int l=1,r=1;
        q[1]=0;
        for(int j=1;j<=m;j++)
        {
            while(l<r && g[q[l + 1]] + s[q[l + 1]] - g[q[l]] - s[q[l]] <= a[j] * (q[l + 1] - q[l])) l++;
            f[j] =min(g[j] , g[q[l]] + a[j] * (j - q[l]) - (s[j] - s[q[l]])); 
            while(l<r && (g[q[r]] + s[q[r]] - g[q[r-1]] - s[q[r - 1]]) * (j - q[r])
                >= (g[j] + s[j] - g[q[r]] - s[q[r]]) * (q[r] - q[r - 1])) r--;
            q[++r] = j;
        }
    }
    cout<< f[m];
}