$A_i=T_i-\sum_{j=1}^{H_i}D_j$也就是饲养员至少要从第$A_i$个时刻之后出发,才能接到$i$的。
根据贪心,肯定是接连续的一段$A_i$更优,因此将$A_i$从小到大排序。
那么$f_{i,j}$表示前$i$个管理员接到前$j$只猫的最短等待时间。
有$f_{i,j}=\min\limits_{0\le k\le j}\{f_{i-1,k}+\sum_{p=k+1}^j(A_{max~A[q\in[k+1,j]]}-A_p)\}$
变为:$f_{i,j}=\min\limits_{0\le k\le j}\{f_{i-1,k}+\sum_{p=k+1}^j(A_{j}-A_p)\}$
记录$A_i$的前缀和$S_i$,那么有$\sum_{p=k+1}^j(A_{j}-A_p)=A_j*(j-k)-(S_j-S_k)$
乱搞之后可以发现,$f_{i,j}=\min\limits_{0\le k\le j}\{f_{i-1,k}+A_j*(j-k)-(S_j-S_k)\}$
转为一条关于$f_{i-1,k}+S_k=A_j*k+f_{i,j}-A_j*j+S_j$的直线。
当截距最小时即为$f_{i,j}$的最小值。
由于斜率不断递增,那么此时就要维护一个下凸壳来满足这个性质。
具体来讲就是对于$k_1<k_2<k_3$,需满足
$\large\frac{f_{i-1,k_2}-f_{i-1,k_1}+S_{k_2}-S_{k_1}}{k_2-k_1}<\frac{f_{i-1,k_3}-f_{i-1,k_2}+S_{k_3}-S_{k_2}}{k_3-k_2}$
队头要满足$\large\frac{f_{i-1,q[l+1]}-f_{i-1,q[l]}+S_{q[l+1]}-S_{q[l]}}{q[l+1]-q[l]}>A_j$,即在当前斜率下,队头是最优的。
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#define gc getchar()
#define ll long long
using namespace std;
const int N=1e5+10;
template<class o>
inline void qr(o &x)
{
x=0;char c=gc;int f=1;
while(c<'0'||c>'9'){if(c=='-')f=-1;c=gc;}
while(c>='0'&&c<='9'){x=x*10+(c^48);c=gc;}
x*=f;
}
void qw(ll x)
{
if(x<0)x=-x,putchar('-');
if(x/10)qw(x/10);
putchar(x%10+48);
}
ll s[N],a[N],d[N],f[2][N];int q[N],u,v;
bool slope(int i,int j,int k){return (f[v][j]+s[j]-f[v][i]-s[i])*(k-j)>=(f[v][k]+s[k]-f[v][j]-s[j])*(j-i);}
int main()
{
int n,m,p;qr(n),qr(m),qr(p);
d[1]=0;for(int i=2;i<=n;i++)qr(d[i]),d[i]+=d[i-1];
for(int i=1,h,t;i<=m;i++)
{
qr(h),qr(t);a[i]=t-d[h];
//s[i]=s[i-1]+a[i];
}
sort(a+1,a+m+1);
for(int i=1;i<=m;i++)s[i]=s[i-1]+a[i];
u=1;v=0;
for(int i=1;i<=m;i++)
f[1][i]=a[i]*i-s[i];
swap(u,v);
for(int i=2;i<=p;i++,swap(u,v))
{
int l=1,r=1;q[1]=0;
for(int j=1;j<=m;j++)
{
while(l<r&&f[v][q[l+1]]+s[q[l+1]]-f[v][q[l]]-s[q[l]]<=a[j]*(q[l+1]-q[l]))++l;
f[u][j]=f[v][q[l]]+a[j]*(j-q[l])-(s[j]-s[q[l]]);
while(l<r&&slope(q[r-1],q[r],j))--r;
q[++r]=j;
}
}
qw(f[v][m]);puts("");
return 0;
}
0 条评论