題目
有 M M M隻貓，雇了 P P P位飼養員。路邊有 N N N座山，從 1 1 1到 N N N編号。第 i i i座山與第 i − 1 i−1 i−1座山之間的距離是 D i D_i Di 。飼養員都住在 1 1 1号山上。第 i i i隻貓去 H i H_i Hi号山玩，玩到時刻 T i T_i Ti停止，然後在原地等飼養員來接。飼養員們必須回收所有的貓。每個飼養員沿着路從 1 1 1号山走到 N N N号山，把各座山上已經在等待的貓全部接走。飼養員在路上行走需要時間，速度為 1 1 1米每機關時間。飼養員在每座山上接貓的時間可以忽略，可以攜帶的貓的數量為無窮大。
你的任務是規劃每個飼養員從 1 1 1号山出發的時間，使得所有貓等待時間的總和盡量小。飼養員出發的時間可以為負。
分析
設 A i = T i − ∑ j = 1 d i A_i=T_i-\sum_{j=1}^{d_i} Ai=Ti−∑j=1di
這道題樸素的動态規劃， f [ i ] [ j ] = m i n { f [ i − 1 ] [ k ] + A [ i ] ∗ ( j − k ) − ( ∑ p = k + 1 j a [ p ] ) } f[i][j]=min\{f[i-1][k]+A[i]*(j-k)-(\sum_{p=k+1}^ja[p])\} f[i][j]=min{f[i−1][k]+A[i]∗(j−k)−(∑p=k+1ja[p])}
是以可以發現這是一個斜率優化，發現這個，還可以發現求的是下凸殼
代碼
#include <cstdio>
#include <algorithm>
typedef long long ll; ll f[2][100001],a[100001];
int n,m,p,d[100001],q[100001];
ll in(){
ll ans=0; int f=1; char c=getchar();
while ((c<48||c>57)&&c!='-') c=getchar();
if (c=='-') c=getchar(),f=-f;
while (c>47&&c<58) ans=ans*10+c-48,c=getchar();
return ans*f;
}
int main(){
n=in(); m=in(); p=in(); ll ans=1ll<<62;
for (register int i=2;i<=n;i++) d[i]=d[i-1]+in();
for (register int i=1,x;i<=m;i++) x=in(),a[i]=in()-d[x];
std::stable_sort(a+1,a+1+m); bool x=0;
for (register int i=2;i<=m;i++) a[i]+=a[i-1];
std::fill(f[x]+1,f[x]+1+m,1ll<<62);
for (register int i=1;i<=p;i++){
int l=1,r=1; q[1]=0; x^=1;
for (int j=1;j<=m;j++){
while (l<r&&f[x^1][q[l+1]]+a[q[l+1]]-a[q[l]]-f[x^1][q[l]]<(a[j]-a[j-1])*(q[l+1]-q[l])) l++;//隊頭沒有用的需要出隊
f[x][j]=f[x^1][q[l]]+(a[j]-a[j-1])*(j-q[l])-(a[j]-a[q[l]]);//動态規劃，當然用了滾動數組
while (l<r&&(f[x^1][q[r]]+a[q[r]]-f[x^1][q[r-1]]-a[q[r-1]])*(j-q[r])>(f[x^1][j]+a[j]-a[q[r]]-f[x^1][q[r]])*(q[r]-q[r-1])) r--;//隊尾不優的出隊
q[++r]=j;//入隊
}
ans=std::min(ans,f[x][m]);
}
return !printf("%lld",ans);
}