Description
Zxr960115 is owner of a large farm. He feeds m cute cats and employs p
feeders. There’s a straight road across the farm and n hills along the
road, numbered from 1 to n from left to right. The distance between
hill i and (i?-?1) is di meters. The feeders live in hill 1.One day, the cats went out to play. Cat i went on a trip to hill hi,
finished its trip at time ti, and then waited at hill hi for a feeder.
The feeders must take all the cats. Each feeder goes straightly from
hill 1 to n without waiting at a hill and takes all the waiting cats
at each hill away. Feeders walk at a speed of 1 meter per unit time
and are strong enough to take as many cats as they want.For example, suppose we have two hills (d2?=?1) and one cat that
finished its trip at time 3 at hill 2 (h1?=?2). Then if the feeder
leaves hill 1 at time 2 or at time 3, he can take this cat, but if he
leaves hill 1 at time 1 he can’t take it. If the feeder leaves hill 1
at time 2, the cat waits him for 0 time units, if the feeder leaves
hill 1 at time 3, the cat waits him for 1 time units.Your task is to schedule the time leaving from hill 1 for each feeder
so that the sum of the waiting time of all cats is minimized.Input
The first line of the input contains three integers
n,?m,?p(2?≤?n?≤?105,?1?≤?m?≤?105,?1?≤?p?≤?100).The second line contains n?-?1 positive integers
d2,?d3,?…,?dn(1?≤?di?<?104).Each of the next m lines contains two integers hi and
ti(1?≤?hi?≤?n,?0?≤?ti?≤?109).Output
Output an integer, the minimum sum of waiting time of all cats.
Please, do not write the %lld specifier to read or write 64-bit
integers in С++. It is preferred to use the cin, cout streams or the
%I64d specifier.
可以发现，每只猫的信息都可以浓缩为一个值：a[i]=t[i]-d[i]，即想要恰好接上这只猫，管理员的出发时间。那么，这只猫的等待时间即为管理员出发时间与这个值的差。
对a数组进行排序，这样每个管理员接走的猫一定是连续的一段。
求a[]的前缀和s[]。
dp[i][j]表示前i个管理员接走前j只猫的最少总等待时间。
那么朴素的状态转移方程即为dp[i][j]=max{dp[i-1][k]+a[j]-a[k+1]+a[j]-a[k+2]+…+a[j]-a[j-1]}。
上式可化简为dp[i-1][k]+a[j]*(j-k)-(s[j]-s[k])。
那么朴素算法的时间复杂度为O(pm^2)。
因为有a[j]*k这一项，j和k无法完全分离，考虑斜率优化。
对于k2>k1，k2比k1优的充要条件是
dp[i-1][k2]+a[j] * (j-k2)-(s[j]-s[k2])<=dp[i-1][k1]+a[j] * (j-k1)-(s[j]-s[k1])
记g(k)=dp[i-1][k]+s[k]
化简得(g(k2)-g(k1))/(k2-k1)<=a[j]。
于是维护k递增、相邻两点斜率也递增，且所有斜率都大于a[j]的单调队列，则任意相邻两点都是左边优于右边，所以队首即为最优解。
维护的时候，因为a[j]单调不减，所以随着j增大，会出现队首两元素的斜率<=a[j]，也就是que[hd+1]优于que[hd]，这样弹出队首。
另外，插入新的j可能使尾部不满足斜率递增。也就是k(que[tl-1],que[tl])<=k(que[tl],j)。（分别记为k1，k2）那么对于以后出现的任何一个j’，如果k1>a[j’]，那么que[tl-1]优于que[tl]。如果k1<=a[j’]，那么k2<=a[j’]，那么j优于que[tl]。所以que[tl]永远不是最优决策，弹出。
时间复杂度优化为O(pm)。
注意边界条件。
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
const long long oo=1000000000233333;
int i,que[100010];
long long len[100010],a[100010],s[100010],dp[110][100010];
long long g(int k)
{
return dp[i-1][k]+s[k];
}
int main()
{
int j,k,m,n,p,q,x,y,z,hd,tl;
scanf("%d%d%d",&n,&m,&p);
for (i=2;i<=n;i++)
{
scanf("%d",&x);
len[i]=len[i-1]+x;
}
for (i=1;i<=m;i++)
{
scanf("%d%d",&x,&y);
a[i]=y-len[x];
}
sort(a+1,a+m+1);
for (i=1;i<=m;i++)
s[i]=s[i-1]+a[i];
for (i=1;i<=m;i++)
dp[0][i]=oo;
for (i=1;i<=p;i++)
{
hd=1;
tl=0;
for (j=0;j<=m;j++)
{
while (hd<tl&&
g(que[hd+1])-g(que[hd])<=
a[j]*(que[hd+1]-que[hd]))
hd++;
dp[i][j]=g(que[hd])+a[j]*(j-que[hd])-s[j];
while (hd<tl&&
(g(j)-g(que[tl]))*
(que[tl]-que[tl-1])<=
(g(que[tl])-g(que[tl-1]))*
(j-que[tl]))
tl--;
que[++tl]=j;
}
}
printf("%I64d\n",dp[p][m]);
}