CF311B Cats Transport（斜率优化）

题目描述

Zxr960115 是一个大农场主。他养了m只可爱的猫子,雇佣了p个铲屎官。这里有一条又直又长的道路穿过了农场，有n个山丘坐落在道路周围，编号自左往右从1到n。山丘i与山丘i-1的距离是Di米。铲屎官们住在1号山丘。

一天，猫子们外出玩耍。猫子i去山丘Hi游玩，在Ti时间结束他的游玩，然后在山丘Hi傻等铲屎官。铲屎官们必须把所有的猫子带上。每个铲屎官直接从H1走到Hn，中间不停下，可以认为不花费时间的把游玩结束的猫子带上。每个铲屎官的速度为一米每单位时间，并且足够强壮来带上任意数量的猫子。

举个栗子，假装我们有两个山丘(D2=1)，有一只猫子，他想去山丘2玩到时间3。然后嘞铲屎官如果在时间2或者时间3从1号山丘出发，他就能抱走猫子。如果他在时间1出发那么就不行(猫子还在玩耍)。如果铲屎官在时间2出发，猫子就不用等他（ΔT=0）。如果他在时间3出发，猫子就要等他1个单位时间。

你的任务是安排每个铲屎官出发的时间，最小化猫子们等待的时间之和。

题解

一个裸的斜率优化……我竟然没有看出来……

每一只猫等待的时间是铲屎官出发的时间-到原点的路程+猫出现的时间

那么我们对每一只猫记录一下-到原点的路程+猫出现的时间，然后sort一下，那么就是把这个序列分成p个区间，每个区间权值为最大的数与每一个数的差之和，然后求最小权值

那么直接上斜率优化

 //minamoto

 #include<iostream>

 #include<cstdio>

 #include<algorithm>

 #define ll long long

 using namespace std;

 #define getc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)

 char buf[<<],*p1=buf,*p2=buf;

 inline int read(){

     #define num ch-'0'

     char ch;bool flag=;int res;

     while(!isdigit(ch=getc()))

     (ch=='-')&&(flag=true);

     for(res=num;isdigit(ch=getc());res=res*+num);

     (flag)&&(res=-res);

     #undef num

     return res;

 }

 const int N=;

 int q[N],h,t,n,m,p,r;ll dp[][N],c[N],d[N],sum[N];

 inline double slope(int j,int k){return (dp[r^][j]+sum[j]-dp[r^][k]-sum[k])*1.0/(j-k);}

 int main(){

     //freopen("testdata.in","r",stdin);

     n=read(),m=read(),p=read();

     for(int i=;i<=n;++i) d[i]=read()+d[i-];

     for(int i=;i<=m;++i){

         int h=read(),t=read();

         c[i]=t-d[h];

     }

     sort(c+,c++m);

     for(int i=;i<=m;++i) sum[i]=sum[i-]+c[i];

     for(int i=;i<=m;++i) dp[][i]=c[i]*(i-)-sum[i-];

     for(int i=;i<=p;++i){

         r=i&;

         h=t=;

         for(int i=;i<=m;++i){

             while(h<t&&slope(q[h],q[h+])<c[i]) ++h;

             dp[r][i]=dp[r^][q[h]]+c[i]*(i-q[h])-sum[i]+sum[q[h]];

             while(h<t&&slope(q[t],q[t-])>slope(q[t],i)) --t;q[++t]=i;

         }

     }

     printf("%lld\n",dp[p&][m]);

     return ;

 }

巴特西

CF311B Cats Transport（斜率优化）

最新文章

热门文章