noi.ac #534 猫

题目链接：戳我

【问题描述】

有n座山，m只猫和p个工作人员。山从左往右编号为1∼n，山i和i−1之间的距离是di米。

有一天，猫都到山上去玩了：第i只猫会到山hi去，并一直玩到时间ti，之后就在那座山等待工作人员来接它。

每个工作人员的线路都是从1走到n，并带走沿途任意只在等待的猫。工作人员速度为每单位时间1米，不能在山上停留。

例如，假设有两个山丘，d2=1，有一只猫要到山2去，在t=3结束它的玩耍。如果工作人员在时间2或时间3离开山1，则他可以带走这只猫，但如果在时间1离开山1，他就不能带走它。如果工作人员在时间2离开山1，则猫等待他0个时间单位，如果工作人员在时间3离开山1，则猫等待他1个时间单位。

你的任务是安排每个工作人员从1出发的时间（整数，可以是负数），使所有猫的等待时间总和最小。

【输入格式】

第一行三个整数n,m,p，表示山、猫、工作人员的数目。

第二行n−1个整数表示d2∼dn。

后面m行，每行两个数hi,ti。

【输出格式】

一个整数，表示所有猫的等待时间总和的最小值。

【数据规模】

40%的数据，m≤1000,p≤100。

80%的数据，m≤5000,p≤1000。

100%的数据，1≤m≤50000,1≤p≤1000。

对于所有数据，2≤n≤1e5,1≤di≤100,1≤hi≤n,0≤ti≤10e5。

斜率优化。

我们考虑每个猫的结束时间减去它的坐标，就相当于所有猫都在节点1，只是结束的时间不同了。

我们再把这个结束的时间排序一下，就可以设\(dp[i][j]\)表示前i只猫，被j个饲养员带走的最小代价了。

转移方程为：\(dp[i][j]=min{dp[i][j],dp[p][j-1]+node[i].num*(i-p)-(sum[i]-sum[p])}\)

其中\(sum[i]\)表示前i只猫的等待时间前缀和，\(node[i].num\)表示该猫等效于在1节点的开始等待时刻。

然后这个朴素DP是40分的。

现在考虑斜率优化：

把式子移项一下：

\(dp[i][j]+node[i].num*p=dp[p][j-1]+node[i].num*i-sum[i]+sum[p]\)

这就有了\(b+kx=y\)的形式

维护下凸壳即可。

下面这份代码被卡常了？？只有90分嘤嘤嘤

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cmath>

#define MAXN 100010

#define ll long long

using namespace std;

inline ll read()

{

    ll x=0,f=1;char ch=getchar();

    while(ch<'0'||ch>'9'){if(ch=='-')f=-1; ch=getchar();}

    while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48); ch=getchar();}

    return x*f;

}

ll n,m,p,tail,head;

ll d[MAXN],dis[MAXN],sum[MAXN],dp[50010][1010],q[MAXN];

struct Node{ll p,num;}node[MAXN];

inline double y(int i,int p){return dp[i][p]+sum[i];}

inline double k(int i,int j,int p)

{

	if(i==j) return 1e9;

	return (y(i,p-1)-y(j,p-1))/(i-j);

}

inline bool cmp(struct Node x,struct Node y){return x.num<y.num;}

int main()

{

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

	for(int i=2;i<=n;i++)

        d[i]=read(),dis[i]=dis[i-1]+d[i];

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

    {

        int x;

		node[i].p=read(),x=read();

        node[i].num=x-dis[node[i].p];

	}

	sort(node+1,node+1+m,cmp);

	for(int i=1;i<=m;i++) sum[i]=sum[i-1]+node[i].num;

	memset(dp,0x3f,sizeof(dp));

    dp[0][0]=0;

	for(int j=1;j<=p;j++)

    {

		tail=head=0;

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

        {

			while(head<tail&&node[i].num>k(q[head],q[head+1],j)) head++;

			dp[i][j]=dp[q[head]][j-1]+node[i].num*i-node[i].num*q[head]-sum[i]+sum[q[head]];

			while(head<tail&&k(q[tail-1],q[tail],j)>k(q[tail],i,j)) tail--;

			q[++tail]=i;

		}

	}

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

	return 0;

}

巴特西